[2021 카카오 채용연계형 인턴십] 표편집 문제풀이

표편집 문제 바로가기 : https://programmers.co.kr/learn/courses/30/lessons/81303

효율성 테스트까지 있어 시간 복잡도를 고려해야하는 문제이다.
삽입과 삭제가 빠르게 하기 위해서 어떤 알고리즘을 선택해야할까 고민을 했지만..
세그먼트 트리로는 어떻게 해야할지 감이 안잡혔고 우선순위 큐를 사용하기로 결정했다.

선택된 행보다 같거나 작은 인덱스를 가지며, 가장 큰 값이 루트 노드로 오도록 left를 설정했고
(-> 선택된 행은 left의 루트노드)
선택된 행보다 큰 인덱스를 가지며, 가장 작은 값이 루트 노드로 오도록 right를 설정했다.

up, down 커맨드를 수행하면서 left <-> right 값이 이동하도록 설정했고
delete 커맨드는 따로 스택을 두어 처리하였다.

import heapq

def solution(n, k, cmds):
    answer = ''
    #left의 루트노드는 선택된 행이다
    left, right, delete, result = [], [], [], []
    for i in range(k + 1):
        heapq.heappush(left, -i)
    for i in range(k + 1, n):
        heapq.heappush(right, i)
    for cmd in cmds:
        if cmd == 'C':
            delete.append(-heapq.heappop(left))
            if right:
                heapq.heappush(left, -heapq.heappop(right))                  
        elif cmd == 'Z':
            d = delete.pop()
            if -left[0] < d:
                heapq.heappush(right, d)
            else:
                heapq.heappush(left, -d)
        else:
            c, x = cmd.split()
            if c == 'U':
                for _ in range(int(x)):
                    heapq.heappush(right, -heapq.heappop(left))                
            elif c == 'D':
                for _ in range(int(x)):
                    heapq.heappush(left, -heapq.heappop(right))                         
    
    while left:
        heapq.heappush(result, (-heapq.heappop(left)))
    while right:
        heapq.heappush(result, (heapq.heappop(right)))
    
    for i in range(n):
        if (not result) or (i != result[0]):
            answer += 'X'
            continue
        else:
            answer += 'O'
            heapq.heappop(result)

    return answer

정확성  테스트
테스트 1 〉	통과 (0.05ms, 10.5MB)
테스트 2 〉	통과 (0.04ms, 10.5MB)
테스트 3 〉	통과 (0.07ms, 10.4MB)
테스트 4 〉	통과 (0.04ms, 10.5MB)
테스트 5 〉	통과 (0.25ms, 10.4MB)
테스트 6 〉	통과 (0.28ms, 10.5MB)
테스트 7 〉	통과 (0.43ms, 10.4MB)
테스트 8 〉	통과 (0.22ms, 10.4MB)
테스트 9 〉	통과 (0.26ms, 10.5MB)
테스트 10 〉	통과 (0.21ms, 10.5MB)
테스트 11 〉	통과 (2.01ms, 10.4MB)
테스트 12 〉	통과 (2.23ms, 10.4MB)
테스트 13 〉	통과 (2.10ms, 10.5MB)
테스트 14 〉	통과 (6.75ms, 10.4MB)
테스트 15 〉	통과 (6.70ms, 10.5MB)
테스트 16 〉	통과 (7.46ms, 10.5MB)
테스트 17 〉	통과 (30.70ms, 10.4MB)
테스트 18 〉	통과 (30.39ms, 10.5MB)
테스트 19 〉	통과 (42.48ms, 10.4MB)
테스트 20 〉	통과 (28.11ms, 10.4MB)
테스트 21 〉	통과 (13.45ms, 10.5MB)
테스트 22 〉	통과 (12.14ms, 10.4MB)
테스트 23 〉	통과 (0.05ms, 10.5MB)
테스트 24 〉	통과 (0.04ms, 10.5MB)
테스트 25 〉	통과 (0.05ms, 10.4MB)
테스트 26 〉	통과 (0.03ms, 10.4MB)
테스트 27 〉	통과 (0.05ms, 10.5MB)
테스트 28 〉	통과 (0.10ms, 10.4MB)
테스트 29 〉	통과 (0.07ms, 10.5MB)
테스트 30 〉	통과 (0.07ms, 10.5MB)
효율성  테스트
테스트 1 〉	통과 (1913.04ms, 56.4MB)
테스트 2 〉	통과 (1839.25ms, 56.4MB)
테스트 3 〉	통과 (2214.56ms, 56.3MB)
테스트 4 〉	통과 (1486.77ms, 62.1MB)
테스트 5 〉	통과 (1661.85ms, 62.1MB)
테스트 6 〉	통과 (1303.02ms, 60.4MB)
테스트 7 〉	통과 (405.69ms, 24.8MB)
테스트 8 〉	통과 (464.45ms, 30.5MB)
테스트 9 〉	통과 (1411.99ms, 61.5MB)
테스트 10 〉	통과 (1301.52ms, 61.3MB)