2021 카카오 채용연계형 인턴십- 표 편집(python)

❓ 문제 - 2021 카카오 코딩테스트 표 편집 문제 - python 풀이법

출처 

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

코딩테스트 연습 - 표 편집

 

 

📝 문제해결법

출처 - 해당 풀이법은 이 블로그를 통해 공부하고 해결하였습니다.

(https://inspirit941.tistory.com/367?category=859228)

 

 

 

1. 문제는 정확성과 효율성 둘 다 만족해야 통과할 수 있는 문제로, 데이터 n의 범위 5 <= n <= 1,000,000을 고려해야함

2. 전체적으로 해결방법은 이진트리 기반의 힙 자료구조와 스택 자료구조를 사용하여 문제를 해결할 수 있음

3. 힙 자료구조

• left, right라는 최소힙을 만듦 -> python heapq 모듈 사용
• heapq 모듈을 사용하면 heapq.pop과 heapq.push 들의 시간복잡도가 O(logN) 이기 때문
• left에는 현재 행 -1 ~ 0 값들이 내림차순으로 정렬된 최대 힙 자료구조
• right에는 현재 행 ~ 마지막 행 값들이 오름차순으로 정렬된 최소 힙 자료구조
• U할 경우 현재 행의 값이 줄어들기 때문에, right에 left 값의 최대 값을 pop해서 push 해주기
• D할 경우 현재 행의 값이 늘어나기 때문에, left에 right 값의 최소 값을 pop해서 push 해주기
• Z할 경우 delete 스택에 있는 값을 pop 해주고, pop 해준 값이 현재 행의 값보다 작다면 left 힙에 push 하기
• Z할 경우 delete 스택에 있는 값을 pop 해주고, pop 해준 값이 현재 행의 값보다 크다면 right 힙에 push 하기

4. 스택 자료구조

• Z할 경우 복구할 때 최신에 삭제된 행의 정보가 복구되므로 스택 자료구조를 사용
• C할 경우 delete로 선언된 스택에 push 해주고, Z할 경우 delete로 선언된 스택에서 pop 하기

 

5. 기억해야 할 구현 방법

• 최소힙은 pop할 때 최솟값이 반환되기 때문에 그대로 사용 가능
• 최대힙은 push할 때 push할 값에 -를 넣어 push하고 pop할 때 최대값을 반환하기 위해 -값을 붙여 pop 해야함

 

 

 

💻 소스코드 

# 2021 카카오 채용연계형 인턴십 - 표 편집
# heapq 라이브러리 사용해서 효율성 해결
import heapq

def solution(n, k, cmd):
    # 현재 위치:right heap의 첫 번째 원소

    left, right, delete = [], [], []
    # 왼쪽은 최대값이 맨 앞에 위치하도록, 오른쪽은 최솟값이 맨 앞에 위치하도록 heap을 구성한다.
    for i in range(n):
        heapq.heappush(right, i)
    for i in range(k):
        heapq.heappush(left, -heapq.heappop(right))

    for c in cmd:
        # U or D인 경우
        if len(c) > 1:
            move = int(c.split()[-1])
            # D(아래로)인 경우
            if c.startswith("D"):
                for _ in range(move):
                # 오른쪽 heap에서 왼쪽 heap으로 값을 이동시킨다.
                    if right:
                        heapq.heappush(left, -heapq.heappop(right))

            # U(위로)인 경우
            elif c.startswith("U"):
                for _ in range(move):
                    # 왼쪽 heap에서 오른쪽 heap으로 값을 이동시킨다.
                    heapq.heappush(right, -heapq.heappop(left))
        elif c == "C":
            # 값을 삭제하되, 가장 최근에 삭제된 값을 복구하기 쉽도록 stack 형태를 사용한다
            delete.append(heapq.heappop(right))

            # 삭제된 행이 가장 마지막 행인 경우 바로 윗 행을 선택하도록 한다.
            if not right:
                heapq.heappush(right, -heapq.heappop(left))
        elif c == "Z":
            # 삭제한 값 복구하기
            repair = delete.pop()

            # 현재 위치보다 값이 작을 경우 left에 넣는다
            if repair < right[0]:
                heapq.heappush(left, -repair)
            else:
                heapq.heappush(right, repair)
    result = []
    while left:
        result.append(-heapq.heappop(left))
    while right:
        result.append(heapq.heappop(right))
    result = set(result)
    answer = ["O" if i in result else "X" for i in range(n)]

    return "".join(answer)