프로그래머스 표 편집

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

프로그래머스

 

뭔가 잘 푼 풀이같지는 않지만 그래도 한번에 풀어서 블로그에 올려본다.

선택된 행을 기준으로 위아래로만 움직이며 주어지는 모든 케이스에서 전체 범위를 벗어나는 케이스는 없다는 조건이 있음으로 deque를 사용해도 될 것 같았으나 삭제한 행을 다시 복구하는 과정에서 순서를 맞춰줘야한다는 조건이 있음으로 heap을 사용해서 풀었다.

주의해야할 점은 아래와 같다.

* 삭제되었다가 복구된 행은 다시 순서를 맞춰줘야함

* 위아래로 움직이면서 전체 표를 벗어나는 움직임은 없다는 점(아래로 끝까지 움직였을때 위로 다시 올라오는 그러한 조건 및 케이스 없음)

* 행을 삭제하고 다음 선택된 행을 선택할 때 조건에 따라 선택된 행이 위로 움직이는지 아래로 움직이는지 구분이 필요

 

import heapq
def solution(n, k, cmds):

    upper_heap = []
    lower_heap = []
    point = -1
    # 현재 가리키고 있는 위치를 기준으로 작으면 upper_heap, 크면 lower_heap
    for i in range(n):
        if i < k: heapq.heappush(upper_heap,-i)
        elif i == k: point = k
        else: heapq.heappush(lower_heap,i)

    removed = []

    for cmd in cmds:
        cmd = cmd.split()


        if cmd[0] == 'D':
            move = int(cmd[1])
            heapq.heappush(upper_heap, -point)
            for i in range(move):
                if i == (move-1):
                    point = heapq.heappop(lower_heap)
                else:
                    heapq.heappush(upper_heap, -heapq.heappop(lower_heap))

        # 대부분의 케이스에서는 현재 포인터를 제거하고 포인터가 아래로 움직이나
        # 상황에 따라서 구분해줄 필요가 있다.
        elif cmd[0] == 'C':
            removed.append(point)
            if not len(upper_heap):
                point = heapq.heappop(lower_heap)
            elif not len(lower_heap):
                point = -heapq.heappop(upper_heap)
            else:
                point = heapq.heappop(lower_heap)

        elif cmd[0] == 'U':
            move = int(cmd[1])
            heapq.heappush(lower_heap, point)
            for i in range(move):
                if i == (move - 1):
                    point = -heapq.heappop(upper_heap)
                else:
                    heapq.heappush(lower_heap, -heapq.heappop(upper_heap))

        # point를 기준으로 upper_heap에 삽입할지 lower_heap에 삽입할지 결정
        elif cmd[0] == 'Z':
            tobe_add = removed.pop()
            if tobe_add < point:
                heapq.heappush(upper_heap, -tobe_add)
            else:
                heapq.heappush(lower_heap, tobe_add)

    # 단순히 정답의 형태로 만들어주기 위한 문자열 작업
    result = ['X']*n
    while upper_heap:
        tmp = -heapq.heappop(upper_heap)
        result[tmp] = 'O'
    result[point] = 'O'
    while lower_heap:
        tmp = heapq.heappop(lower_heap)
        result[tmp] = 'O'

    return ''.join(result)