자료구조
- 인덱스 트리(세그먼트 트리)
문제 간단 설명
- 위 표에서, 파란색 칸은 현재 커서의 위치를 의미합니다. 커서는 위, 아래로 이동할 수 있고 커서가 있는 행을 삭제할 수 있습니다.
- 가장 최근에 삭제된 행을 원래대로 복구할 수 있습니다.
1
2
3
4
"U X": 현재 선택된 행에서 X칸 위에 있는 행을 선택합니다.
"D X": 현재 선택된 행에서 X칸 아래에 있는 행을 선택합니다.
"C" : 현재 선택된 행을 삭제한 후, 바로 아래 행을 선택합니다. 단, 삭제된 행이 가장 마지막 행인 경우 바로 윗 행을 선택합니다.
"Z" : 가장 최근에 삭제된 행을 원래대로 복구합니다. 단, 현재 선택된 행은 바뀌지 않습니다.
풀이
데이터가 있고, 없고를 1과 0으로 표현할 수 있습니다. 처음 상태는 1이고, 명령어 C로 지워진 것들은 0이 됩니다. (이미지 출처 : kakao tech)
위 그림에서, 하늘색 부분이 커서라고 합시다. “U 3” 명령을 만났을 때 합이 처음 3이 되는 부분으로 커서가 이동합니다.
이 아이디어로 구현하기 위해, 구간 합을 빠르게 구할 수 있는 세그먼트 트리를 사용할 수 있습니다.
명령어별 풀이
- [U, D 명령어] X 현재 커서 위치부터 이동할 수 있는 최대 거리까지를 범위로 잡고 Binary Search를 통해 구간 합이 X가 되는 위치를 구합니다.
- [C 명령어] 현재 커서 위치를 0으로 바꿔줍니다. (이때 필요한 작업은 세그먼트 트리 업데이트). 커서 위치는 Z 명령어를 위해 스택에 저장합니다. 그 후, 커서는 바로 아래 행을 선택해야 하는데, 구간합이 1인 위치를 Binary Search를 통해 찾습니다.
- [Z 명령어] C 명령어에서 지워진 커서의 위치를 스택에서 꺼낸 다음, 세그먼트 트리를 업데이트 해줍니다.
코드
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
116
117
118
119
120
121
122
123
124
125
#include <string>
#include <vector>
#include <stack>
#include <iostream>
int table[1<<21];
std::stack<int> st;
std::string answer = "";
int seg_sum(int l, int r, int n)
{
int ans = 0;
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l & 1) ans += table[l++];
if (r & 1) ans += table[--r];
}
return ans;
}
void update(int idx, int val, int n)
{
table[idx + n] = val;
for (idx += n ; idx > 1 ; idx >>= 1)
{
table[idx >> 1] = table[idx] + table[idx ^ 1];
}
}
void init_seg(int n)
{
for (int i = n - 1 ; i > 0 ; i--)
table[i] = table[i << 1] + table[i << 1 | 1];
}
int b_search(int start, int end, int num, int flag, int n)
{
int mid, val, s = start, e = end;
if (flag)
{
while (start <= end)
{
mid = (start + end) / 2;
val = seg_sum(s, mid + 1, n);
if (val >= num)
end = mid - 1;
else
start = mid + 1;
}
return (start);
}
else // up
{
while (start <= end)
{
mid = (start + end) / 2;
val = seg_sum(mid, e + 1, n);
if (val >= num)
start = mid + 1;
else
end = mid - 1;
}
return (end);
}
return (0);
}
std::string solution(int n, int k, std::vector<std::string> cmd) {
int cmd_size = cmd.size();
int num, cursor = k , how;
int x;
std::string op;
for (int i = 0 ; i < n ; i++)
answer += "O";
for (int i = 0 ; i < n ; i++)
table[i + n] = 1;
init_seg(n);
for (int i = 0 ; i < cmd_size ; i++)
{
op = cmd[i][0];
if (op == "D")
{
x = 2;
std::string v = "";
int d_size = cmd[i].size();
while (x < d_size)
v += cmd[i][x++];
num = std::stoi(v);
cursor = b_search(cursor + 1, n - 1, num, 1, n);
}
else if (op == "U")
{
x = 2;
std::string v = "";
int d_size = cmd[i].size();
while (x < d_size)
v += cmd[i][x++];
num = std::stoi(v);
cursor = b_search(0, cursor - 1, num, 0, n);
}
else if (op == "C")
{
update(cursor, 0, n);
st.push(cursor);
answer[cursor] = 'X';
int plus_how = b_search(cursor + 1, n - 1, 1, 1, n);
if (plus_how >= 0 && plus_how < n)
cursor = plus_how;
else
cursor = b_search(0, cursor - 1, 1, 0, n);
}
else if (op == "Z")
{
int z_val = st.top();
st.pop();
update(z_val, 1, n);
answer[z_val] = 'O';
}
}
return answer;
}
회고
- 재귀를 통한 세그먼트 트리는 시간초과가 났습니다.