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

문제 바로가기

자료구조

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

문제 간단 설명

• 위 표에서, 파란색 칸은 현재 커서의 위치를 의미합니다. 커서는 위, 아래로 이동할 수 있고 커서가 있는 행을 삭제할 수 있습니다.
• 가장 최근에 삭제된 행을 원래대로 복구할 수 있습니다.

"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를 통해 찾습니다.