[프로그래머스] 코딩테스트 연습 - 표 편집(Python)

코딩테스트 연습 - 표 편집 [2021 카카오 채용연계형 인턴십]

풀이

참 Python이 낯설게 느껴지고 많은 걸 배울 수 있었던 문제였습니다.

그리고 3번의 풀이 끝에 간신히 해결했습니다. 사실 Python에 대한 지식이 얕아 틀린 방법이 맞는 방법이라고 생각한 게 시간을 가장 많이 잡아먹은 요인인 것 같습니다. 머리가 안 좋아 몸도 고생하고 머리도 고생한 타입...ㅎㅎ

어떠한 시도를 했는지 적어 보겠습니다.

 

(모든 풀이 과정에서 deque을 이용한 stack을 사용했습니다!)

1. 0~n의 정수를 담은 list를 deque으로 만들어 삽입/삭제를 하는 방식으로 구현

   위의 방식으로 풀이를 해보면 효율성을 하나도 통과하지 못합니다. 그 이유는 deque의 특성을 생각해보면 알 수 있습니다. deque은 linked list가 아닌 양방향 삽입/삭제가 가능한 queue이기 때문에 deque 중간에서 삽입/삭제를 하는 것은 list보다 더 많은 시간이 들게 만듭니다.

 

2. 1번 방법에서 0~n의 정수를 담은 list를 deque으로 만들지 않고 list로 사용

   해당 방식으로 풀이를 해보면 놀랍게도 효율성에서 2문제는 통과합니다. 결국 문제에서 말하는 표를 만들기 위한 자료구조에 deque은 적합하지 않다는 것이죠. 길이가 엄청 커지면 삽입/삭제의 시간이 굉장히 비효율적일 테니까요.

 

3. 2번 방법에서 복구작업을 할 때 복구되는 위치를 이분탐색으로 검색.

   개인적으로는 이분탐색을 하면 해결될 줄 알았지만 어림도 없었습니다ㅎㅎ.. 여전히 효율성 2문 제 만 통과하더라고요. 

 

4. "O"*n을 담은 list에서 삭제되는 인덱스만 "X"로 변경하고 인덱스 이동시에 while문을 사용해 "X"는 건너뛰어가며 이동(정확성 해설의 풀이와 같습니다.)

   이 방식을 사용해서 가장 좋았던 결과가 효율성 1~5번까지 시간초과가시간 초과가 뜨지 않았던 경우 같습니다. 하지만 여전히 나머지는 시간 초과가 발생하더라고요.

 

사실 위의 방법들을 시도하면서 가장 큰 문제점은 deque이 linked list인 줄 알았다는 점입니다... 

답답한 마음에 어떤 방법을 써야 복잡도가 가장 빠른지 검색을 하다 보니 deque은 linked list가 아닌 양방향 queue이고 Python에는 linked list의 모듈이 없다는 것을 알게 되었습니다. (큰 충격으로 절대 잊히지 않을 개념인 것 같습니다ㅎ)

그래서 거의 2년 만에 node class를 직접 만들어 linked list를 구현해서 풀이해보니 그 재서야 통과를 하더군요.. 허허...

Linked list풀이는 아래와 같습니다. (dictionary를 사용한 풀이도 가능합니다)

 

Code

from collections import deque
class node():
    def __init__(self, value):
        self.next = None
        self.prev = None
        self.value = value

def solution(n, k, cmd):
    answer = ["O" for i in range(n)]
    p = node(0)
    curr = p
    for idx in range(1, n):     # linked list 생성
        newnode = node(idx)
        newnode.prev = p
        p.next = newnode
        p = newnode
        if idx == k+1:      # 시작지점 Node
            curr = p.prev
    stack = deque()         # 삭제를 저장할 stack
    for c in cmd:
        if c[0] == "D":
            for i in range(int(c[2:])):
                curr = curr.next
        elif c[0] == "U":
            for i in range(int(c[2:])):
                curr = curr.prev
        elif c[0] == "C":       # 삭제 명령어
            stack.appendleft(curr)
            answer[curr.value] = "X"
            if curr.next == None:       # 마지막 node일 경우
                curr.prev.next = None
                curr = curr.prev
            elif curr.prev == None:     # 처음 node일 경우
                curr.next.prev = None
                curr = curr.next
            else:                       # 중간 node일 경우
                curr.prev.next = curr.next
                curr.next.prev = curr.prev
                curr = curr.next
        elif c[0] == "Z":       # 복구 명령어
            latest = stack.popleft()
            answer[latest.value] = "O"
            if latest.next == None:     # 마지막 node일 경우
                latest.prev.next = latest
            elif latest.prev == None:   # 처음 node일 경우
                latest.next.prev = latest
            else:                       # 중간 node일 경우
                latest.next.prev = latest
                latest.prev.next = latest
    return "".join(answer)

 

 

문제 설명

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

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

위 그림에서 파란색으로 칠해진 칸은 현재 선택된 행을 나타냅니다. 단, 한 번에 한 행만 선택할 수 있으며, 표의 범위(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

입출력 예

n	k	cmd	result
8	2	["D 2","C","U 3","C","D 4","C","U 2","Z","Z"]	"OOOOXOOO"
8	2	["D 2","C","U 3","C","D 4","C","U 2","Z","Z","U 1","C"]	"OOXOXOOO"