[프로그래머스] 표 편집 (Java)
[프로그래머스] 표 편집 풀이
◾ 문제
문제 설명
[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]
업무용 소프트웨어를 개발하는 니니즈웍스의 인턴인 앙몬드는 명령어 기반으로 표의 행을 선택, 삭제, 복구하는 프로그램을 작성하는 과제를 맡았습니다. 세부 요구 사항은 다음과 같습니다
위 그림에서 파란색으로 칠해진 칸은 현재 선택된 행을 나타냅니다. 단, 한 번에 한 행만 선택할 수 있으며, 표의 범위(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 이하인 경우만 입력으로 주어집니다.
- 표의 모든 행을 제거하여, 행이 하나도 남지 않는 경우는 입력으로 주어지지 않습니다.
- 본문에서 각 행이 제거되고 복구되는 과정을 보다 자연스럽게 보이기 위해 ”이름” 열을 사용하였으나, ”이름”열의 내용이 실제 문제를 푸는 과정에 필요하지는 않습니다. ”이름”열에는 서로 다른 이름들이 중복없이 채워져 있다고 가정하고 문제를 해결해 주세요.
- cmd의 각 원소는
- 표의 범위를 벗어나는 이동은 입력으로 주어지지 않습니다.
- 원래대로 복구할 행이 없을 때(즉, 삭제된 행이 없을 때)
"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과 같습니다.
10번째 명령어 "U 1"을 수행하면 ”어피치”가 적힌 2행이 선택되며, 마지막 명령어 "C"를 수행하면 선택된 행을 삭제하고, 바로 아래 행이었던 ”제이지”가 적힌 행을 선택합니다.
따라서 처음 주어진 표의 상태와 최종 표의 상태를 비교하면 다음과 같습니다.
제한시간 안내
- 정확성 테스트 : 10초
- 효율성 테스트 : 언어별로 작성된 정답 코드의 실행 시간의 적정 배수
주어진 표에서 행을 위아래로 선택 이동하고, 현재 선택된 행을 삭제하거나 가장 최근에 삭제된 행을 복구하는 명령어들을 수행한 후의 최종 표 상태를 반환하는 문제다.
◾ 알고리즘 [접근 방식]
ArrayList 의 한계
가장 먼저 떠올릴 수 있는 방법은 자바의 ArrayList를 사용하여 표의 행을 관리하는 것이다.
ArrayList를 사용한다면 “C” : 행 삭제 혹은 ”Z” : 행 복구 명령어를 수행할 때마다 뒤에 있는 모든 요소들의 인덱스를 한 칸씩 당기거나 밀어야 한다. 따라서 ArrayList를 사용하면 삽입/삭제의 시간 복잡도는 $O(N)$이 된다.
이 문제에서 처음 표의 행 개수 $n$은 최대 $1,000,000$이고, 주어지는 명령어 배열 cmd의 크기는 최대 $200,000$이다.
최악의 경우, $200,000$번의 명령어 동안 계속해서 리스트의 맨 앞부분을 삭제하고 복구한다면 $1,000,000 \times 200,000 = 200,000,000,000$ (2,000억) 번의 연산이 발생하게 되며, 무조건 시간 초과가 발생한다. 시간초과를 피하기 위해선 삭제 / 복구 로직을 $O(1)$ 만에 처리해야 한다.
그러므로 이 문제는 삽입/삭제가 $O(1)$로 가능한 연결리스트를 사용해야 한다.
자바 내장 LinkedList 사용?
자바에는 LinkedList 클래스로 연결리스트를 기본적으로 제공하고 있고, LinkedList 는 삽입/삭제 로직이 O(1) 로 가능하고 이중 연결 리스트로 구현되어 있다. 이 문제를 푸는 데 적합한 자료구조같지만 사용한다면 반드시 시간초과가 발생한다.
노드 직접 접근 불가
자바의 LinkedList는 배열이나 ArrayList처럼 특정 인덱스에 바로 접근(Random Access)이 불가능하다. 원하는 노드에 접근하려면 양 끝 노드인 head나 tail에서부터 한칸 한칸 이동해서 목적 노드까지 이동해야 한다.
"C" 명령어를 수행하기 위해 list.remove(선택된 행 인덱스) 메서드를 사용할텐데, 삭제 로직 자체는 $O(1)$ 로 가능하지만, 삭제할 위치를 찾는 데 $O(N)$의 시간이 걸리므로, 최종 시간복잡도가 $O(N)$이 되는 것이다.
"Z" 명령어를 수행하기 위해 add(복구할 행 인덱스, 행) 메서드를 사용할 때도 마찬가지로, 삽입 로직은 $O(1)$ 이지만 복구할 위치까지 도달하는 데 $O(N)$의 시간이 걸린다.
삽입/삭제, 접근 모두 한 번만에 가능한 방법을 찾아야 한다.
이중 연결 리스트 직접 구현
노드의 삽입과 삭제, 그리고 현재 선택된 행에 접근을 $O(1)$에 처리하기 위해선 이중 연결 리스트(Doubly Linked List)를 직접 구현해야 한다.
각 행을 노드(Node)로 직접 만들고 현재 가리키는 행을 Node curr 로 설정하고 관리하면, 현재 노드를 삭제할 때 순차탐색 없이 앞뒤 노드의 포인터만 서로 연결해 주면 되므로 최종적으로 $O(1)$만에 처리할 수 있다.
이중 연결 리스트의 삽입 및 삭제 연산에 대한 자세한 개념은 아래 포스팅 참고
[Data Structure] 이중 연결 리스트(Doubly Linked List)
최근 삭제된 행 복구 : 스택 활용
가장 최근 삭제된 행을 복구하는 “Z” 명령어를 수행하기 위해 후입선출(LIFO) 구조인 스택에 삭제된 행을 저장하고 복구가 필요할 때 꺼내서 복구한다.
이중 연결 리스트에서는 노드를 삭제하더라도, 삭제된 노드 객체 자신은 여전히 원래의 prev와 next를 기억하고 있다. 스택에서 꺼낸 순서(역순)대로 복구하면 주변 노드들의 상태가 보장되므로, 원래 자리에 그대로 포인터만 다시 연결해 주면 된다.
1. 초기 상태
- 현재 연결 상태:
[1] <-> [2] <-> [3] <-> [4] - 스택:
[](비어있음)
2. “2번 행” 삭제
- 2번 노드는 삭제되더라도 여전히 자신의 앞뒤 노드를 기억하고 있다. (prev: 1번, next: 3번)
- 2번이 삭제되었으므로
- 1번 노드의 next = 3번
- 3번 노드의 prev = 1번 으로 변경된다.
- 현재 연결 상태:
[1] <-> [3] <-> [4] - 스택:
[2번]
3. “3번 행” 삭제
- 마찬가지로 3번 노드는 삭제되더라도 앞뒤 노드를 기억하고 있다. (prev: 1번, next: 4번)
- 3번이 삭제되었으므로
- 1번 노드의 next = 4번
- 1번 노드의 prev = 1번 으로 변경된다.
- 현재 연결 상태:
[1] <-> [4] - 스택:
[2번, 3번]
4. 첫 번째 복구 (“Z” 명령어 수행)
- 스택은 LIFO 구조이므로 3번 노드가 먼저 나온다.
- 3번 노드는 자신이 기억하던 1번과 4번 사이로 다시 들어간다.
- 현재 연결 상태:
[1] <-> [3] <-> [4] - 스택:
[2번]
5. 두 번째 복구 (“Z” 명령어 수행)
- 스택에 남아있던 2번 노드가 나온다.
- 2번 노드가 기억하는 앞 뒤 노드는 1번과 3번이다. 따라서 2번 노드는 1번과 3번 사이에 자신을 연결하면 된다.
- 최종 연결 상태:
[1] <-> [2] <-> [3] <-> [4]
◾ 핵심 로직
n개의Node객체를 생성하고 배열에 담아둔다. (나중에 최종 결과 문자열을 만들 때 순서대로 접근하기 위함)- 각 노드의
prev와next를 초기화하여 이중 연결 리스트를 구성한다.- 이때, 맨 앞과 맨 뒤에 각각 더미(Dummy) 노드인
head와tail을 달아주면 엣지 케이스(맨 처음/끝 요소 삭제) 처리 시NullPointerException을 방지할 수 있어 코드가 매우 깔끔해진다.
- 이때, 맨 앞과 맨 뒤에 각각 더미(Dummy) 노드인
- 명령어 배열을 순회하며 다음을 수행한다.
U/D: 현재 행을 가리키는curr에서 시작하여prev/next포인터를 타고 주어진 숫자만큼 이동한다.C(삭제): 현재 노드의 상태를 삭제됨으로 표시하고 스택에 넣는다. 이후prev와next노드를 서로 직접 연결하여 현재 노드를 리스트에서 고립시킨다. 현재 노드가tail바로 앞이었다면 위로(prev), 아니면 아래로(next) 이동한다.Z(복구): 스택에서 가장 최근 노드를 꺼내 삭제 상태를 해제한다. 꺼낸 노드가 기억하고 있는prev와next를 이용해, 주변 노드들이 다시 자신을 가리키도록 포인터를 복구한다.
◾ 코드
자바 정답 코드
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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
import java.util.*;
class Solution {
// 이중 연결 리스트를 구성할 노드 클래스
static class Node {
Node prev;
Node next;
boolean isRemoved; // 최종 결과 판별을 위한 삭제 여부 플래그
}
static Node curr; // 현재 선택된 노드
static Node head; // 더미 헤드 노드
static Node tail; // 더미 테일 노드
static Node[] nodes; // 인덱스 기반 빠른 접근 및 최종 결과 확인용 배열
static Stack<Node> removed; // 삭제된 행을 담아둘 스택 (복구용)
public String solution(int n, int k, String[] cmds) {
removed = new Stack<>();
nodes = new Node[n];
// 1. n개의 노드 생성
for (int i = 0; i < n; i++) {
nodes[i] = new Node();
}
// 2. 더미 head 연결
head = new Node();
head.next = nodes[0];
nodes[0].prev = head;
// 3. 노드 간의 이중 연결 리스트 구성
for (int i = 0; i < n - 1; i++) {
nodes[i].next = nodes[i + 1];
nodes[i + 1].prev = nodes[i];
}
// 4. 더미 tail 연결
tail = new Node();
tail.prev = nodes[n - 1];
nodes[n - 1].next = tail;
// 초기 커서 위치 설정
curr = nodes[k];
// 5. 명령어 처리
for (String cmd : cmds) {
char command = cmd.charAt(0);
switch (command) {
case 'U':
up(Integer.parseInt(cmd.substring(2)));
break;
case 'D':
down(Integer.parseInt(cmd.substring(2)));
break;
case 'C':
remove();
break;
case 'Z':
restore();
break;
}
}
// 6. 최종 결과 문자열 생성
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) {
if (!nodes[i].isRemoved) sb.append("O");
else sb.append("X");
}
return sb.toString();
}
// 지정된 칸 수만큼 위로(prev) 이동
static void up(int offset) {
for (int i = 0; i < offset; i++) {
curr = curr.prev;
}
}
// 지정된 칸 수만큼 아래로(next) 이동
static void down(int offset) {
for (int i = 0; i < offset; i++) {
curr = curr.next;
}
}
// 현재 행 삭제
static void remove() {
curr.isRemoved = true;
removed.push(curr);
// 앞뒤 노드 연결로 현재 노드 끊어내기
curr.prev.next = curr.next;
curr.next.prev = curr.prev;
// 커서 이동: 삭제된 행이 마지막 행인 경우 윗 행을, 아니면 아랫 행을 선택
if (curr.next == tail) curr = curr.prev;
else curr = curr.next;
}
// 가장 최근 삭제된 행 복구
static void restore() {
Node node = removed.pop();
node.isRemoved = false;
// 끊어졌던 앞뒤 노드의 포인터를 다시 복구된 노드로 연결
node.prev.next = node;
node.next.prev = node;
}
}
◾ 결과
댓글 0