PS - 문자열과 알파벳과 쿼리 (C++ 코드)
프로그래머스 문자열과 알파벳과 쿼리 해법
1. 해법 추론
쿼리별 동작을 달리하는 문제는 쿼리별로 효율적으로 해결할 수 있는 방법을 구상하여 결합하는 방식이 가장 쉬운 접근방법이다.
1-1. 쿼리 1
1번 쿼리를 먼저 보자. 1번 쿼리의 핵심은 x번 문자와 y번 문자가 속한 문자열이 같은지 다른지를 알아내는 문제로 환원할 수 있다.
따라서 각 고유번호에 대해 문자열 번호가 매핑되는 자료구조를 구상해놓으면 (vector, map등의 경우에 대해)\(O(1)\)시간 내에 쿼리의 답을 알아낼 수 있을 것이다.
1-2. 쿼리 2
2번 쿼리는 x번 문자가 속한 문자열의 원소(문자)들 중 word에 포함된 알파벳 전부를 새로운 문자열에 저장하는 쿼리이다.
사실 이 쿼리를 그대로 시행하려면 최악의 경우 문자열 전체를 확인해야하는 일이 생길 수 있기 때문에 이 방법은 아니라는 것을 알 수 있다.
2번 쿼리의 특징은 한 문자열 내의 알파벳 한 종류를 통채로 이동시킨다는 것이다.
따라서 애초에 \(s\)를 알파벳 별로 따로 묶음을 만들어 알파벳 그룹을 형성하고 이 그룹이 문자열 번호를 가리키도록 하는 자료구조를 구상해 놓으면, 2번 쿼리는 \(O(1)\)의 시간 정도로 실행 가능하다.
추가로 고유번호에 알파벳을 매핑해놓은 테이블을 만들어놓으면 쿼리 1에서 구상한 자료구조 없이도 1번 쿼리을 수행할 수가 있다. 다만 알파벳 묶음의 자료구조 형태에 따라서 계산복잡도는 달라질 수 있다. 따라서 고유번호를 기준으로한 균형잡힌 이진탐색트리 정도를 고안해볼 만 하다.
굳이 위에서 추가로 자료구조를 언급한 이유는 자료구조를 단순화하기 위해서이다.
또한 Balanced-BST를 사용하면 고유번호 조회과정에서 검색 시간이 \(O(\log s)\)가 되기 때문에 1, 2번 쿼리의 실질적인 시간량은 \(O(\log s)\)가 됨을 유의해야한다.
1-3. 쿼리 3
3번 쿼리는 2번과 비슷한데 x번 문자가 속한 문자열이 아니라 순수하게 x~y번 문자 중에서 새로운 문자열으로 이동할 문자를 정하는 것이다.
2번 쿼리에서 구상한 자료구조를 사용하게 된다면 word의 각 문자에 대해서 x~y번 문자에 해당하는 문자들을 각각 갱신해야 하니 \(O(s)\)의 시간 복잡도를 가지게 된다.
따라서 임의의 범위를 효율적으로 갱신할 수 있는 자료구조를 고안해야한다. 그리고 2번 쿼리의 동작에는 영향을 미치면 안된다.
범위를 효율적으로 갱신하는 자료구조는 지연 전파 세그먼트 트리가 있다. 세그먼트 트리는 부분합을 구하는 도구지만 약간 변형하여 알파벳 그룹 내 서브그룹을 가리키는 정보를 가진 자료구조로 사용할 수 있다.
3번 쿼리에 의해서 알파벳 그룹은 한 덩어리처럼 움직일 수 없고 그 안에는 여러 서브그룹이 존재할 수 있게 되고 이 서브그룹을 효율적으로 갱신해야한다.
알파벳 별로 존재하는 세그먼트 트리 내에 존재하는 고유번호 각각에 서브그룹 인덱스를 부여하고 이 인덱스가 문자열 번호를 가리키게 한다면 3번 쿼리를 \(O(\log s)\)시간에 실행가능하다.
중요한 것은 2번 쿼리와의 충돌 가능성을 잘 해결하는 것인데 지연전파 기능을 이용하면 2번 쿼리가 실행될 때 x~y번에 해당하는 문자들이 가리키는 서브그룹 인덱스를 지연갱신하여 영향을 회피할 수 있다.
1-4. 쿼리 4
4번 쿼리는 2번 3번과는 좀 다르다. 새로운 문자열을 만드는 것이 아니라 기존 문자열을 합치는 쿼리이다.
우선 기존에 만들어놓은 자료구조를 이용해보면, 4번 쿼리는 문자열을 가리키는 각 알파벳 별 서브그룹을 합치는 문제로 환원 가능하다.
단순히 합쳐질 서브그룹의 원소 모두를 합칠 서브그룹의 원소로 바꾸는 것은 그 그룹의 크기에 따라 최악의 경우 \(O(s)\)수준이 될 수 있다. 따라서 다른 방법을 고안해야한다.
여러 집합들을 쉽게 합치는 알고리즘이 있는데, 바로 서로소 집합 알고리즘이다.
어떤 서브그룹이 다른 서브그룹을 가리키게 하면 두 서브그룹은 하나가 된 것으로 간주한다면, 먼저 만들어진 서브그룹이 나중에 만들어진 서브그룹을 가리키게 한다면 \(O(1)\)수준의 시간으로 쿼리를 해결할 수 있게 된다.
1-5. 쿼리 5
5번쿼리는 시키는 대로 한다. 다만 만들어진 문자열의 타임스탬프가 필요한데, 그 부분은 1~4번 쿼리를 진행하면서 사용한 문자열 그룹 id를 사용하면 될 것이다.
사실 쿼리 5를 단순 구현하면 \(O(s)\)이지만 쿼리의 맨 마지막 1회만 실행되기 때문에 상관없다.
따라서 설명을 생략하겠다.
2. 코드(C++)
세그먼트 트리를 이용하는데 필요한 데이터는 서브그룹id 뿐이니 실제 트리를 만드는 게 아니라 지연 갱신 트리만을 사용해도 괜찮다.
또한, solution함수에서 세그먼트 트리와 문자별 집합을 쉽게 이용하기 위해서 구조체를 사용했는데 사실 클래스를 사용해서 접근지정자를 엄격하게 적용하여 코드를 짜는 것이 바람직하다.
Union-Find자료구조에서는 경로압축 알고리즘을 사용했다.
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
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
#include <string>
#include <vector>
#include <sstream>
using namespace std;
struct SegTree {
int N;
vector<int> lazy;
void init(int n) {
N = n;
lazy.assign(4 * N + 4, -1);
lazy[1] = 0;
}
void push(int node, int start, int end) {
if (lazy[node] != -1 && start != end) {
lazy[node * 2] = lazy[node];
lazy[node * 2 + 1] = lazy[node];
lazy[node] = -1;
}
}
void update(int node, int start, int end, int left, int right, int val) {
if (right < start || end < left) return;
if (left <= start && end <= right) {
lazy[node] = val;
return;
}
push(node, start, end);
int mid = (start + end) / 2;
update(node * 2, start, mid, left, right, val);
update(node * 2 + 1, mid + 1, end, left, right, val);
}
int query(int node, int start, int end, int idx) {
if (start == end) return lazy[node];
push(node, start, end);
int mid = (start + end) / 2;
if (idx <= mid) return query(node * 2, start, mid, idx);
else return query(node * 2 + 1, mid + 1, end, idx);
}
};
struct CharManager {
int c;
SegTree tree;
vector<int> parent;
vector<int> cg_to_string;
vector<int> string_cg;
void init(int n, int char_idx) {
c = char_idx;
tree.init(n);
parent.reserve(450005);
cg_to_string.reserve(450005);
string_cg.reserve(200005);
parent.push_back(0);
cg_to_string.push_back(0);
string_cg.push_back(0);
}
int new_cg(int g) {
int id = parent.size();
parent.push_back(id);
cg_to_string.push_back(g);
return id;
}
int find(int x) {
if (parent[x] == x) return x;
return parent[x] = find(parent[x]);
}
void add_string() {
int g = string_cg.size();
int id = new_cg(g);
string_cg.push_back(id);
}
};
vector<string> solution(string s, vector<string> query) {
int N = s.length();
vector<CharManager> chars(26);
for (int i = 0; i < 26; ++i) {
chars[i].init(N, i);
}
int groupId = 0;
vector<string> answer;
for (const string& q : query) {
stringstream ss(q);
int type;
ss >> type;
if (type == 1) {
int x, y;
ss >> x >> y;
int c_x = s[x - 1] - 'a';
int c_y = s[y - 1] - 'a';
int g_x = chars[c_x].cg_to_string[chars[c_x].find(chars[c_x].tree.query(1, 1, N, x))];
int g_y = chars[c_y].cg_to_string[chars[c_y].find(chars[c_y].tree.query(1, 1, N, y))];
answer.push_back(g_x == g_y ? "YES" : "NO");
}
else if (type == 2) {
int x;
string word;
ss >> x >> word;
int c_x = s[x - 1] - 'a';
int g_x = chars[c_x].cg_to_string[chars[c_x].find(chars[c_x].tree.query(1, 1, N, x))];
groupId++;
for (int i = 0; i < 26; ++i) chars[i].add_string();
bool present[26] = { false };
for (char c : word) present[c - 'a'] = true;
for (int c = 0; c < 26; ++c) {
if (present[c]) {
int old_root = chars[c].find(chars[c].string_cg[g_x]);
int new_root = chars[c].find(chars[c].string_cg[groupId]);
chars[c].parent[old_root] = new_root;
chars[c].string_cg[g_x] = chars[c].new_cg(g_x);
}
}
}
else if (type == 3) {
int x, y;
string word;
ss >> x >> y >> word;
groupId++;
for (int i = 0; i < 26; ++i) chars[i].add_string();
bool present[26] = { false };
for (char c : word) present[c - 'a'] = true;
for (int c = 0; c < 26; ++c) {
if (present[c]) {
int new_root = chars[c].find(chars[c].string_cg[groupId]);
chars[c].tree.update(1, 1, N, x, y, new_root);
}
}
}
else if (type == 4) {
int x, y;
ss >> x >> y;
int c_x = s[x - 1] - 'a';
int c_y = s[y - 1] - 'a';
int g_x = chars[c_x].cg_to_string[chars[c_x].find(chars[c_x].tree.query(1, 1, N, x))];
int g_y = chars[c_y].cg_to_string[chars[c_y].find(chars[c_y].tree.query(1, 1, N, y))];
if (g_x != g_y) {
if (g_x > g_y) swap(g_x, g_y);
for (int c = 0; c < 26; ++c) {
int root_x = chars[c].find(chars[c].string_cg[g_x]);
int root_y = chars[c].find(chars[c].string_cg[g_y]);
if (root_x != root_y) {
chars[c].parent[root_y] = root_x;
}
chars[c].string_cg[g_y] = chars[c].new_cg(g_y);
}
}
}
else if (type == 5) {
vector<vector<int>> counts(groupId + 1, vector<int>(26, 0));
for (int i = 1; i <= N; ++i) {
int c = s[i - 1] - 'a';
int g = chars[c].cg_to_string[chars[c].find(chars[c].tree.query(1, 1, N, i))];
counts[g][c]++;
}
for (int g = 0; g <= groupId; ++g) {
string temp = "";
for (int c = 0; c < 26; ++c) {
if (counts[g][c] > 0) {
if (!temp.empty()) temp += " ";
temp += (char)('a' + c);
temp += " ";
temp += to_string(counts[g][c]);
}
}
if (!temp.empty()) {
answer.push_back(temp);
}
}
}
}
return answer;
}
후기) 문제 특성상 문자열 파싱 도구가 필요해서 string stream을 사용했는데, 정말 파이썬이 그리웠었다.
오타 혹은 잘못된 정보가 있다면 댓글 이메일 등등으로 알려주시면 감사하겠습니다. (꾸벅)