[프로그래머스 lv3] 표 편집 (파이썬, 문자열, LinkedList)

문제 설명

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

업무용 소프트웨어를 개발하는 니니즈웍스의 인턴인 앙몬드는 명령어 기반으로 표의 행을 선택, 삭제, 복구하는 프로그램을 작성하는 과제를 맡았습니다. 세부 요구 사항은 다음과 같습니다

위 그림에서 파란색으로 칠해진 칸은 현재 선택된 행을 나타냅니다. 단, 한 번에 한 행만 선택할 수 있으며, 표의 범위(0행 ~ 마지막 행)를 벗어날 수 없습니다. 이때, 다음과 같은 명령어를 이용하여 표를 편집합니다.

• "U X": 현재 선택된 행에서 X칸 위에 있는 행을 선택합니다.
• "D X": 현재 선택된 행에서 X칸 아래에 있는 행을 선택합니다.
• "C" : 현재 선택된 행을 삭제한 후, 바로 아래 행을 선택합니다. 단, 삭제된 행이 가장 마지막 행인 경우 바로 윗 행을 선택합니다.
• "Z" : 가장 최근에 삭제된 행을 원래대로 복구합니다. 단, 현재 선택된 행은 바뀌지 않습니다.

예를 들어 위 표에서 "D 2"를 수행할 경우 아래 그림의 왼쪽처럼 4행이 선택되며, "C"를 수행하면 선택된 행을 삭제하고, 바로 아래 행이었던 "네오"가 적힌 행을 선택합니다(4행이 삭제되면서 아래 있던 행들이 하나씩 밀려 올라오고, 수정된 표에서 다시 4행을 선택하는 것과 동일합니다).

다음으로 "U 3"을 수행한 다음 "C"를 수행한 후의 표 상태는 아래 그림과 같습니다.

다음으로 "D 4"를 수행한 다음 "C"를 수행한 후의 표 상태는 아래 그림과 같습니다. 5행이 표의 마지막 행 이므로, 이 경우 바로 윗 행을 선택하는 점에 주의합니다.

다음으로 "U 2"를 수행하면 현재 선택된 행은 2행이 됩니다.

위 상태에서 "Z"를 수행할 경우 가장 최근에 제거된 "라이언"이 적힌 행이 원래대로 복구됩니다.

다시한번 "Z"를 수행하면 그 다음으로 최근에 제거된 "콘"이 적힌 행이 원래대로 복구됩니다. 이때, 현재 선택된 행은 바뀌지 않는 점에 주의하세요.

이때, 최종 표의 상태와 처음 주어진 표의 상태를 비교하여 삭제되지 않은 행은 "O", 삭제된 행은 "X"로 표시하면 다음과 같습니다.

처음 표의 행 개수를 나타내는 정수 n, 처음에 선택된 행의 위치를 나타내는 정수 k, 수행한 명령어들이 담긴 문자열 배열 cmd가 매개변수로 주어질 때, 모든 명령어를 수행한 후 표의 상태와 처음 주어진 표의 상태를 비교하여 삭제되지 않은 행은 O, 삭제된 행은 X로 표시하여 문자열 형태로 return 하도록 solution 함수를 완성해주세요.

 

제한 사항

• 5 ≤ n ≤ 1,000,000
• 0 ≤ k < n
• 1 ≤ cmd의 원소 개수 ≤ 200,000
  • cmd의 각 원소는 "U X", "D X", "C", "Z" 중 하나입니다.
  • X는 1 이상 300,000 이하인 자연수이며 0으로 시작하지 않습니다.
  • X가 나타내는 자연수에 ',' 는 주어지지 않습니다. 예를 들어 123,456의 경우 123456으로 주어집니다.
  • cmd에 등장하는 모든 X들의 값을 합친 결과가 1,000,000 이하인 경우만 입력으로 주어집니다.
  • 표의 모든 행을 제거하여, 행이 하나도 남지 않는 경우는 입력으로 주어지지 않습니다.
  • 본문에서 각 행이 제거되고 복구되는 과정을 보다 자연스럽게 보이기 위해 "이름" 열을 사용하였으나, "이름"열의 내용이 실제 문제를 푸는 과정에 필요하지는 않습니다. "이름"열에는 서로 다른 이름들이 중복없이 채워져 있다고 가정하고 문제를 해결해 주세요.
• 표의 범위를 벗어나는 이동은 입력으로 주어지지 않습니다.
• 원래대로 복구할 행이 없을 때(즉, 삭제된 행이 없을 때) "Z"가 명령어로 주어지는 경우는 없습니다.
• 정답은 표의 0행부터 n - 1행까지에 해당되는 O, X를 순서대로 이어붙인 문자열 형태로 return 해주세요.

정확성 테스트 케이스 제한 사항

• 5 ≤ n ≤ 1,000
• 1 ≤ cmd의 원소 개수 ≤ 1,000

효율성 테스트 케이스 제한 사항

• 주어진 조건 외 추가 제한사항 없습니다.

 

입출력 예

입출력 예 설명

입출력 예 #1

문제의 예시와 같습니다.

입출력 예 #2

다음은 9번째 명령어까지 수행한 후의 표 상태이며, 이는 입출력 예 #1과 같습니다.

10번째 명령어 "U 1"을 수행하면 "어피치"가 적힌 2행이 선택되며, 마지막 명령어 "C"를 수행하면 선택된 행을 삭제하고, 바로 아래 행이었던 "제이지"가 적힌 행을 선택합니다.

따라서 처음 주어진 표의 상태와 최종 표의 상태를 비교하면 다음과 같습니다.

제한시간 안내

• 정확성 테스트 : 10초
• 효율성 테스트 : 언어별로 작성된 정답 코드의 실행 시간의 적정 배수

---

나의 풀이

효율성 테스트를 통과하지 못해 아주 많은 시간을 투자한 문제이다. 쉽게 생각할 수 있는 리스트로 접근을 했었는데 리스트로 접근해서는 (선형 탐색의 경우)효율성 테스트를 통과할 수 없다.

이 문제에서 요구하는 것은 요소의 삭제, 복구, 조건 탐색 이렇게 3가지라고 생각된다. 리스트로 접근했을 때는 조건 탐색(삭제 되지 않은 행을 탐색)할 때 선형적으로 탐색하기 때문에 효율성 테스트를 통과하지 못했다. 그래서 조건 탐색을 다른 방법으로 시도해야 한다.

나는 양방향 LinkedList 자료구조를 사용해서 풀이했다.

일반적인 LinkedList는 다음 요소의 정보만 가지고 있는 단방향성이지만 이 문제에서는 이전 노드와 다음 노드를 자유롭게 탐색해야 하므로 이전 요소 정보와 다음 요소 정보를 가지는 양방향성이어야 한다.

LinkedList 노드의 구성

 

N = 10 ** 9


class Node:
    survived = True

    def __init__(self, p, n):
        self.prev = p if p >= 0 else None
        self.next = n if n < N else None


def solution(n, k, command):
    global N
    N = n
    table = {i: Node(i - 1, i + 1) for i in range(n)}
    current = k
    removed = []

    for cmd in command:
        if cmd == "C":  # 1. 삭제

        elif cmd == "Z": # 2. 실행 취소
 
        else:
            c, amount = cmd.split()
            if c == "U":
                # 3. 위로

            elif c == "D":
                # 4. 아래로
                
    return # ...

우선 기본 뼈대는 위와 같이 구성했다.

Node 클래스는 현재 삭제 여부와 이전 노드 정보, 다음 노드 정보를 가진다. 이전 노드가 없으면 prev에 None을, 다음 노드가 없으면 next에 None을 저장한다.

solution() 함수의 table은 사전 자료 구조이며 table[i] 는 i번째 노드의 인스턴스가 들어간다.

 

다음은 cmd에 따라 1. 삭제, 2. 실행 취소, 3. 탐색 순서대로 처리하는 과정이다.

1. 삭제

LinkedList 노드의 구성

노드가 위와 같이 구성되어 있을 때 현재 노드(10번 노드)를 삭제한다고 하면 현재 노드의 이전 노드와 다음 노드를 연결해주어야 한다.

LinkedList 노드 삭제

이전 노드의 next에 다음 노드를 지정하고, 다음 노드의 prev에 이전 노드를 지정하면 된다.

 

만약 현재 노드가 맨 앞 노드이거나 맨 뒤 노드일 경우 prev나 next가 None일 수 있다. 조건문으로 None을 체크한 후 일련의 과정을 수행하면 된다.

문제에서 삭제한 노드를 복구하는 부분이 있었으므로 removed라는 스택에 삭제한 현재 노드를 push 한다.

table[current].survived = False # 현재 노드의 survived를 False로 변경
removed.append(current) # 스택에 현재 노드 push

prev, next = table[current].prev, table[current].next # prev: 이전 노드, next: 다음 노드

# 이전 노드의 next를 다음 노드에 연결
if prev is not None: table[prev].next = table[current].next
# 다음 노드의 prev를 이전 노드에 연결
if next is not None: table[next].prev = table[current].prev

# 노드 제거
if table[current].next is None:  # 다음 노드가 없음
    current = table[current].prev
else:  # 다음 노드가 있음
    current = table[current].next

 

2. 실행 취소 (최근 삭제한 노드 복구)

최근 삭제된 노드들은 removed 스택에 저장되어 있다. 마지막으로 삭제된 노드를 pop으로 꺼낸다.

꺼낸 노드의 상태(survived)를 True로 변경한다.

복구된 노드의 prev와 next에는 삭제 당시 이전 노드와 다음 노드의 정보가 보존되어 있다. (table에서 삭제하지 않았으므로)

그럼 다시 prev 노드의 next와 next 노드의 prev를 복구된 노드로 연결한다.

LinkedList 노드 복구

물론 삭제될 당시 맨 앞 노드였거나 맨 뒤 노드였을 경우 prev나 next가 None일 수 있다. 조건문으로 None을 검사 후 일련의 과정을 수행하면 된다.

recovered = removed.pop() # 스택에서 최근 삭제 노드 꺼내기
table[recovered].survived = True # 꺼낸 노드의 survived를 True로 변경

prev, next = table[recovered].prev, table[recovered].next # prev: 이전 노드, next: 다음 노드

# 이전 노드의 next를 자신으로 연결
if prev is not None: table[prev].next = recovered
# 다음 노드의 prev를 자신으로 연결
if next is not None: table[next].prev = recovered

 

3. 탐색

LinkedList에서 탐색은 오히려 쉽다. 앞으로 탐색하는 경우 prev만 따라가면 되고, 뒤로 탐색하는 경우 next만 따라가면 된다.

앞으로 탐색

for _ in range(int(amount)):
    current = table[current].prev

뒤로 탐색

for _ in range(int(amount)):
    current = table[current].next

 

4. 정답 출력

만약 현재 노드의 survived가 True라면 삭제되지 않은 것이고, False라면 삭제된 노드인 것이다. survived가 True라면 O를, False라면 X를 출력하면 된다. 리스트 컴프리헨션을 사용해 한 라인으로 구현했다.

''.join(["O" if table[i].survived else "X" for i in range(n)])

 

전체 코드

N = 10 ** 9


class Node:
    survived = True

    def __init__(self, p, n):
        self.prev = p if p >= 0 else None
        self.next = n if n < N else None


def solution(n, k, command):
    global N
    N = n
    table = {i: Node(i - 1, i + 1) for i in range(n)}
    current = k
    removed = []

    for cmd in command:
        if cmd == "C":  # 삭제
            table[current].survived = False
            removed.append(current)

            prev, next = table[current].prev, table[current].next
            # 앞 노드의 next를 뒷 노드에 연결
            if prev is not None: table[prev].next = table[current].next
            # 뒷 노드의 prev를 앞 노드에 연결
            if next is not None: table[next].prev = table[current].prev

            # 노드 제거
            if table[current].next is None:  # 다음 노드가 없음
                current = table[current].prev
            else:  # 다음 노드가 있음
                current = table[current].next

        elif cmd == "Z": # 실행 취소
            recovered = removed.pop()
            table[recovered].survived = True

            # 앞 노드의 next를 자신으로 연결
            prev, next = table[recovered].prev, table[recovered].next
            if prev is not None: table[prev].next = recovered
            # 뒤 노드의 prev를 자신으로 연결
            if next is not None: table[next].prev = recovered


        else:
            c, amount = cmd.split()
            if c == "U":
                # 위로
                for _ in range(int(amount)):
                    current = table[current].prev

            elif c == "D":
                # 아래로
                for _ in range(int(amount)):
                    current = table[current].next
    return ''.join(["O" if table[i].survived else "X" for i in range(n)])

 

채점 결과

 

---

카카오 공식 해설

이동하기