2021 카카오 채용연계형 인턴십 3번 - 표 편집
자료구조
•
인덱스 트리(세그먼트 트리)
문제 간단 설명
•
위 표에서, 파란색 칸은 현재 커서의 위치를 의미합니다. 커서는 위, 아래로 이동할 수 있고 커서가 있는 행을 삭제할 수 있습니다.
•
가장 최근에 삭제된 행을 원래대로 복구할 수 있습니다.
"U X": 현재 선택된 행에서 X칸 위에 있는 행을 선택합니다.
"D X": 현재 선택된 행에서 X칸 아래에 있는 행을 선택합니다.
"C" : 현재 선택된 행을 삭제한 후, 바로 아래 행을 선택합니다. 단, 삭제된 행이 가장 마지막 행인 경우 바로 윗 행을 선택합니다.
"Z" : 가장 최근에 삭제된 행을 원래대로 복구합니다. 단, 현재 선택된 행은 바뀌지 않습니다.
Plain Text
복사
풀이
위 그림에서, 하늘색 부분이 커서라고 합시다. "U 3" 명령을 만났을 때 합이 처음 3이 되는 부분으로 커서가 이동합니다.
명령어별 풀이
•
[U, D 명령어] X
현재 커서 위치부터 이동할 수 있는 최대 거리까지를 범위로 잡고 Binary Search를 통해 구간 합이 X가 되는 위치를 구합니다.
•
[C 명령어]
현재 커서 위치를 0으로 바꿔줍니다. (이때 필요한 작업은 세그먼트 트리 업데이트). 커서 위치는 Z 명령어를 위해 스택에 저장합니다. 그 후, 커서는 바로 아래 행을 선택해야 하는데, 구간합이 1인 위치를 Binary Search를 통해 찾습니다.
•
[Z 명령어]
C 명령어에서 지워진 커서의 위치를 스택에서 꺼낸 다음, 세그먼트 트리를 업데이트 해줍니다.
코드
#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;
}
C++
복사
회고
•
재귀를 통한 세그먼트 트리는 시간초과가 났습니다.
