[프로그래머스] 표 편집

https://programmers.co.kr/learn/courses/30/lessons/81303

코딩테스트 연습 - 표 편집

 

4단계 문제 '호텔 방 배정' 처럼 재귀함수를 이용하여 위치를 찾고 'C' 일 때, k 를 remove 에 담아 처리하려고 했으나, 'Z' 때문에 구현하기가 힘들 것 같았다.

 

그래서 생각해낸 것이 heapq 를 이용하였다. 'Z' 의 경우에도 복원된 행의 위치를 queue 에 담기만 하면 제 위치를 찾아가기 때문이다.

 

현재 위치는 right 의 가장 첫 원소로 한다. 예를 들어, n = 8, k = 2 인 경우,

 

left = [-1, 0], right = [2, 3, 4, 5, 6, 7] 이며 right[0] 이 현재 위치라면 k 는 0 으로 설정해준다.

'C' 또는 'Z' 가 나타날 때 k 만큼 이동해준 뒤 삭제 또는 복원해 주면 된다.

 

k 가 예를 들어 -2 라면 left 에 있는 가장 큰 번호 2개를 right 에 담는다.

반대로, k 가 2 라면 right 에 있는 가장 작은 번호 2개를 left 에 담는다. right 의 길이가 0 이 될 경우는 마지막 행의 위치가 삭제되었으므로 삭제된 후 위치를 바로 앞의 행(left 에 있는 가장 큰 번호)로 한다. 즉, right 에 -left[0] 을 담는다.

 

'C' 라면 현재 위치의 번호를 remove 에 담고, 'Z' 라면 remove 의 마지막 원소를 현재 위치랑 비교하여 작으면 left, 크면 right 에 담는다.

 

마지막으로 remove 에 있는 번호들이 삭제된 번호이므로 해당하는 index 를 'X' 로 바꿔준다.

 

import heapq

def solution(n, k, cmd):
    answer = ['O'] * n
    right = []
    left = []
    remove = []
    
    for i in range(n):
        if i < k:
            heapq.heappush(left, -i)
        else:
            heapq.heappush(right, i)

    k = 0
    
    for i in cmd:
        if i[0] == 'U':
            k -= int(i.split()[1])
        
        elif i[0] == 'D':
            k += int(i.split()[1])
        
        elif i[0] == 'C':
            if k < 0:
                for i in range(-k-1):
                    heapq.heappush(right, -heapq.heappop(left))
                
                remove.append(-heapq.heappop(left))
            else:
                for i in range(k):
                    heapq.heappush(left, -heapq.heappop(right))
                
                remove.append(heapq.heappop(right))
                
                if not right:
                    heapq.heappush(right, -heapq.heappop(left))
        
            k = 0
            
        else:
            n = remove.pop()
    
            if k < 0:
                for i in range(-k):
                    heapq.heappush(right, -heapq.heappop(left))
            else:
                for i in range(k):
                    heapq.heappush(left, -heapq.heappop(right))
        
            if right[0] < n:
                heapq.heappush(right, n)
            else:
                heapq.heappush(left, -n)
            
            k = 0

    for i in remove:
        answer[i] = 'X'
    
    answer = ''.join(answer)
    
    return answer

print(solution(8, 2, ['D 2', 'C', 'U 3', 'C', 'D 4', 'C', 'U 2', 'Z', 'Z'])) # OOOOXOOO