[TIL]Day 136

탐욕법(Greedy)

• 부분적인 최적해가 전체적인 최적해
• 알고리즘의 각 단계에서 그 순간에 최적이라고 생각되는 것을 선택
• 현재의 선택이 마지막 해답의 최적성을 해치지 않을 때 ==
  앞 단계에서의 선택이 이후 단계에서의 동작에 의한 해의 최적성에 영향을 주지 않음

프로그래머스 탐욕법 문제 풀기

체육복

• 빌려줄 학생들을 "정해진 순서"로 살펴야하고, 이 "정해진 순서"에 따라 우선하여 빌려줄 방향을 정해야함.
  학생 수만큼 배열을 확보하고, 여기에 각자가 가지고 있는 체육복의 수를 기록한다. -> 번호 순서대로 "스캔"하면서 빌려줄 관계를 정한다.
• ! 코드 구현의 편의성을 위해 앞 뒤에 원소 추가
• 학생수는 극단적으로 많고 여벌의 체육복을 가져온 학생은 매우 적다면?
  - 여벌의 체육복을 가져온 학생들의 번호를 정렬(O(klogk)시간 복잡도이기 때문에 n이 크고 k가 작을때만 의미있음. n은 전체길이 k는 여벌의 체육복 길이)하고, 이것을 하나하나 순서대로 살펴보면서 빌려줄 수 있는 다른 학생(해시)을 찾아서 처리한다.

방법 1 - O(n)

def solution(n, lost, reserve):
    students = [1] + [1 for _ in range(n)] + [1]
    for i in reserve:
        students[i] = 2
    for i in lost:
        students[i] -= 1
    for i in range(len(students)):
        if students[i] == 0:
            if students[i+1] == 2:
                students[i+1] = 1
                students[i] = 1
            elif students[i-1] == 2:
                students[i-1] = 1
                students[i] = 1
    return students.count(1) + students.count(2) -2

def solution(n, lost, reserve):
    u = [1]*(n+2)
    for i in reserve:
        u[i] += 1
    for i in lost:
        u[i] -= 1
    for i in range(1,n+1):
        if u[i-1] == 0 and u[i] == 2:
            u[i-1:i+1] = [1,1]
        elif u[i] == 2 and u[i+1] == 0:
            u[i:i+2] = [1,1]
    return len([x for x in u[1:-1] if x > 0])

방법 2 - O(klogk)

def solution(n,lost,reserve):
	s = set(lost) & set(reserve)
    l = set(lost) - s
    r = set(reserve) - s
    for x in sorted(r):
    	if x -1 in l:
        	l.remove(x - 1)
        elif x + 1 in l:
        	l.remove(x + 1)
    return n - len(l)

def solution(n, lost, reserve):
    answer = n - len(lost)
    tmp = list(set(lost) & set(reserve))
    for i in tmp:
        lost.remove(i)
        reserve.remove(i)
    answer = answer + len(tmp)    
    for i in lost:
        for j in reserve:
            if j in [i-1,i,i+1]:
                reserve.remove(j)

                answer = answer + 1
                break
    return answer

d[i]를 0이 아닌 1로 두는 이유는 0이면 if절에서 False로 인식하기 때문

def solution(n, lost, reserve):
    lost_set = set(lost)
    reserve_set = set(reserve)
    intersection = lost_set & reserve_set
    reserve_set -= intersection
    lost_set -= intersection
    reserve = sorted(list(reserve_set)) 
    d = {}
    for i in lost_set:
        d[i] = 1
    for i in reserve:
        if d.get(i-1,False):
            del d[i-1]
        elif d.get(i+1,False):
            del d[i+1]
    return n - len(d)

큰 수 만들기

• 앞 자리에 큰수가 와야함.
• 앞 자리에서부터 하나씩 골라서 담되, 지금 담으려는 것보다 작은 것들은 도로 뺀다. 단, 뺄수 있는 수효에 도달할때까지
• 큰 수가 앞 자리에, 작은 수가 뒷 자리에 놓이도록
• (제약조건) 뺄수 있는 숫자의 수
• 주의할점 이미 순차적으로 되어있는 경우

def solution(number, k):
    stack = [number[0]]
    for num in number[1:]:
        while k > 0 and stack and stack[-1] < num:
            k -= 1
            stack.pop()
        stack.append(num)
        
    if k > 0:
        stack = stack[:-k]
    return ''.join(stack)

조이스틱

• 맨처음 생각한 방식은 순차적으로 보면서 왼쪽 혹은 오른쪽으로 이동하는것 중에 최적을 계산했다.
• 그러나 순차적이기보단 지금내 포커스에서 가장 이동이 적은 것들을 처리해나가는 방식이 맞다.
• 예를들어 ABAAAACHG가 있으면 1번 인덱스 B 처리하고 마지막 인덱스 G 처리하고 그다음 G옆에 H 처리하고 이런식으로...

def solution(name):
    answer = 0
    items = [(i,min(ord(t) - ord("A"),ord("Z") - ord(t) + 1)) for i,t in enumerate(name) if t != 'A']
    cur = 0
    while items:
        tmp = get_min_move(items,cur,len(name))
        answer += tmp[0]
        cur = tmp[1]
    return answer

def get_min_move(items,cur,length):
    tmps = []
    for i,item in enumerate(items):
        tmps.append((abs(item[0]-cur),i,item[1],item[0]))
        tmps.append((cur+length-item[0],i,item[1],item[0]))
    min_item = min(tmps)
    items.pop(min_item[1])
    return (min_item[0]+min_item[2],min_item[3])