Search
Duplicate
♣️

2021 카카오 채용연계형 인턴십 3번 - 표 편집

간단소개
팔만코딩경 컨트리뷰터
ContributorNotionAccount
주제 / 분류
알고리즘
태그
Scrap
8 more properties

2021 카카오 채용연계형 인턴십 3번 - 표 편집

자료구조

인덱스 트리(세그먼트 트리)

문제 간단 설명

위 표에서, 파란색 칸은 현재 커서의 위치를 의미합니다. 커서는 위, 아래로 이동할 수 있고 커서가 있는 행을 삭제할 수 있습니다.
가장 최근에 삭제된 행을 원래대로 복구할 수 있습니다.
"U X": 현재 선택된 행에서 X칸 위에 있는 행을 선택합니다. "D X": 현재 선택된 행에서 X칸 아래에 있는 행을 선택합니다. "C" : 현재 선택된 행을 삭제한 후, 바로 아래 행을 선택합니다. 단, 삭제된 행이 가장 마지막 행인 경우 바로 윗 행을 선택합니다. "Z" : 가장 최근에 삭제된 행을 원래대로 복구합니다. 단, 현재 선택된 행은 바뀌지 않습니다.
Plain Text

풀이

데이터가 있고, 없고를 1과 0으로 표현할 수 있습니다. 처음 상태는 1이고, 명령어 C로 지워진 것들은 0이 됩니다. (이미지 출처 : kakao tech)
위 그림에서, 하늘색 부분이 커서라고 합시다. "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++

회고

재귀를 통한 세그먼트 트리는 시간초과가 났습니다.