[Programmers] 표 편집 (Python3)
문제 설명
업무용 소프트웨어를 개발하는 니니즈웍스의 인턴인 앙몬드는 명령어 기반으로 표의 행을 선택, 삭제, 복구하는 프로그램을 작성하는 과제를 맡았습니다. 세부 요구 사항은 다음과 같습니다
| 행번호 | 이름 |
|---|---|
| 0 | 무지 |
| 1 | 콘 |
| 2 | 어피치 * |
| 3 | 제이지 |
| 4 | 프로도 |
| 5 | 네오 |
| 6 | 튜브 |
| 7 | 라이언 |
위 그림에서 파란색으로 칠해진 칸은 현재 선택된 행을 나타냅니다. 단, 한 번에 한 행만 선택할 수 있으며, 표의 범위(0행 ~ 마지막 행)를 벗어날 수 없습니다. 이때, 다음과 같은 명령어를 이용하여 표를 편집합니다.
- “U X”: 현재 선택된 행에서 X칸 위에 있는 행을 선택합니다.
- “D X”: 현재 선택된 행에서 X칸 아래에 있는 행을 선택합니다.
- “C” : 현재 선택된 행을 삭제한 후, 바로 아래 행을 선택합니다. 단, 삭제된 행이 가장 마지막 행인 경우 바로 윗 행을 선택합니다.
- “Z” : 가장 최근에 삭제된 행을 원래대로 복구합니다. 단, 현재 선택된 행은 바뀌지 않습니다.
예를 들어 위 표에서 “D 2”를 수행할 경우 아래 그림의 왼쪽처럼 4행이 선택되며, “C”를 수행하면 선택된 행을 삭제하고, 바로 아래 행이었던 “네오”가 적힌 행을 선택합니다(4행이 삭제되면서 아래 있던 행들이 하나씩 밀려 올라오고, 수정된 표에서 다시 4행을 선택하는 것과 동일합니다).
| 행번호 | 이름 |
|---|---|
| 0 | 무지 |
| 1 | 콘 |
| 2 | 어피치 |
| 3 | 제이지 |
| 4 | 프로도 * |
| 5 | 네오 |
| 6 | 튜브 |
| 7 | 라이언 |
| 행번호 | 이름 |
|---|---|
| 0 | 무지 |
| 1 | 콘 |
| 2 | 어피치 |
| 3 | 제이지 |
| 4 | 네오 * |
| 5 | 튜브 |
| 6 | 라이언 |
다음으로 “U 3”을 수행한 다음 “C”를 수행한 후의 표 상태는 아래 그림과 같습니다.
|행번호| 이름|
|:—:|:—:|
|0| 무지|
|1| 콘 * |
|2| 어피치|
|3| 제이지|
|4| 네오|
|5| 튜브|
|6| 라이언|
| 행번호 | 이름 |
|---|---|
| 0 | 무지 |
| 1 | 어피치 * |
| 2 | 제이지 |
| 3 | 네오 |
| 4 | 튜브 |
| 5 | 라이언 |
다음으로 “D 4”를 수행한 다음 “C”를 수행한 후의 표 상태는 아래 그림과 같습니다. 5행이 표의 마지막 행 이므로, 이 경우 바로 윗 행을 선택하는 점에 주의합니다.
| 행번호 | 이름 |
|---|---|
| 0 | 무지 |
| 1 | 어피치 |
| 2 | 제이지 |
| 3 | 네오 |
| 4 | 튜브 |
| 5 | 라이언 * |
| 행번호 | 이름 |
|---|---|
| 0 | 무지 |
| 1 | 어피치 |
| 2 | 제이지 |
| 3 | 네오 |
| 4 | 튜브 * |
다음으로 “U 2”를 수행하면 현재 선택된 행은 2행이 됩니다.
| 행번호 | 이름 |
|---|---|
| 0 | 무지 |
| 1 | 어피치 |
| 2 | 제이지 * |
| 3 | 네오 |
| 4 | 튜브 |
위 상태에서 “Z”를 수행할 경우 가장 최근에 제거된 “라이언”이 적힌 행이 원래대로 복구됩니다.
| 행번호 | 이름 |
|---|---|
| 0 | 무지 |
| 1 | 어피치 |
| 2 | 제이지 * |
| 3 | 네오 |
| 4 | 튜브 |
| 5 | 라이언 |
다시한번 “Z”를 수행하면 그 다음으로 최근에 제거된 “콘”이 적힌 행이 원래대로 복구됩니다. 이때, 현재 선택된 행은 바뀌지 않는 점에 주의하세요.
| 행번호 | 이름 |
|---|---|
| 0 | 무지 |
| 1 | 콘 |
| 2 | 어피치 |
| 3 | 제이지 * |
| 4 | 네오 |
| 5 | 튜브 |
| 6 | 라이언 |
이때, 최종 표의 상태와 처음 주어진 표의 상태를 비교하여 삭제되지 않은 행은 “O”, 삭제된 행은 “X”로 표시하면 다음과 같습니다.
| 행번호 | 이름 | |
|---|---|---|
| 0 | 무지 | O |
| 1 | 콘 | O |
| 2 | 어피치 | O |
| 3 | 제이지 | O |
| 4 | 프로도 | X |
| 5 | 네오 | O |
| 6 | 튜브 | O |
| 7 | 라이언 | O |
처음 표의 행 개수를 나타내는 정수 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”|
입출력 예 설명
입출력 예 #1
문제의 예시와 같습니다.
입출력 예 #2
다음은 9번째 명령어까지 수행한 후의 표 상태이며, 이는 입출력 예 #1과 같습니다.
| 행번호 | 이름 |
|---|---|
| 0 | 무지 |
| 1 | 콘 |
| 2 | 어피치 |
| 3 | 제이지 * |
| 4 | 네오 |
| 5 | 튜브 |
| 6 | 라이언 |
10번째 명령어 “U 1”을 수행하면 “어피치”가 적힌 2행이 선택되며, 마지막 명령어 “C”를 수행하면 선택된 행을 삭제하고, 바로 아래 행이었던 “제이지”가 적힌 행을 선택합니다.
| 행번호 | 이름 |
|---|---|
| 0 | 무지 |
| 1 | 콘 |
| 2 | 어피치 * |
| 3 | 제이지 |
| 4 | 네오 |
| 5 | 튜브 |
| 6 | 라이언 |
| 행번호 | 이름 |
|---|---|
| 0 | 무지 |
| 1 | 콘 |
| 2 | 제이지 * |
| 3 | 네오 |
| 4 | 튜브 |
| 5 | 라이언 |
따라서 처음 주어진 표의 상태와 최종 표의 상태를 비교하면 다음과 같습니다.
| 행번호 | 이름 | |
|---|---|---|
| 0 | 무지 | O |
| 1 | 콘 | O |
| 2 | 어피치 | X |
| 3 | 제이지 | O |
| 4 | 프로도 | X |
| 5 | 네오 | O |
| 6 | 튜브 | O |
| 7 | 라이언 | O |
제한시간 안내
정확성 테스트 : 10초
효율성 테스트 : 언어별로 작성된 정답 코드의 실행 시간의 적정 배수
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
def solution(n, k, cmd):
answer = ''
linked_list = {i: [i - 1, i + 1] for i in range(1, n+1)} #n=8일때 1~8까지
answer = ["O" for i in range(1,n+1)]
stack = []
k += 1
for c in cmd:
if c[0] == "D":
for _ in range(int(c[2:])):
k = linked_list[k][1]
if c[0] == "U":
for _ in range(int(c[2:])):
k = linked_list[k][0]
if c[0] == "C":
prev, next = linked_list[k]
answer[k-1] = "X"
stack.append([prev, next, k])
if next == n+1:
k = linked_list[k][0]
else:
k = linked_list[k][1]
if prev == 0:
linked_list[next][0] = prev
elif next == n+1:
linked_list[prev][1] = next
else:
linked_list[prev][1] = next
linked_list[next][0] = prev
if c[0] == "Z":
prev, next, now = stack.pop()
answer[now-1] = "O"
if prev == 0:
linked_list[next][0] = now
elif next == n+1:
linked_list[prev][1] = now
else:
linked_list[prev][1] = now
linked_list[next][0] = now
return "".join(answer)
문제풀이
어제 모의고사에서 정확성만 통과 했던 문제이다.
원래는 리스트로 풀었었는데, 효율성 테스트에서 너무 많이 시간차가 나서 아예 리스트로 풀어서는 효율성을 통과하지 못하는 테스트였다는 것을 알아채고 빠르게 4번으로 넘어갔어야 헀다는 생각이 들었다.
이 문제는 시간 복잡도를 만족시키려면 결국 링크드리스트로 풀이해야하는데, 링크드 리스트는 모든 배열이 연결되어 있어, 만약 3에 접근하고 싶으면 1, 2를 거쳐야만 3으로 갈 수 있다. 따라서 탐색에는 O(N)의 시간이 걸린다. 하지만 삭제와 삽입에는 언제나 O(1)의 시간복잡도를 갖기 때문에 이 문제와 같이 삭제를 하고 이를 기록해두었다가 다시 복구하는 기능에는 링크드리스트가 가장 효율적으로 문제를 해결 할 수 있는 구조였다.
클래스를 사용해서 링크드리스트를 만드는 방식과 내가 푼 풀이처럼 딕셔너리를 이용해서 푸는 방식이 있는데,
아무래도 딕셔너리를 사용하는 편이 코드가 간단해서 딕셔너리 방식으로 풀었다.
링크드 리스트로 해당 데이터 컬럼을 만들어 준뒤, 만약 삭제 요청이 들어오면 해당 데이터를 실제로 삭제하는 것이 아니라, 이전 노드와 다음노드의 관계를 끊어줌으로써 연관관계만 제거해 줄뿐 실제로 해당 데이터를 삭제하지는 않는다. 따라서 Z요청, 되돌리기 요청이 들어오면 해당 노드를 기억해놓다가 불러와서 다시 이전의 노드와 다음 노드의 연관관계를 이어주면 되기 때문에 Z요청을 처리 할때도 따로 탐색을 해서 위치를 바꿀 필요가 없다.
리스트에 시간복잡도를 묻는 문제가 나오면 꼭 링크드리스트로 구현하는게 더 효율적인지는 않는지 확인을 꼭 해봐야겠다.
댓글남기기