문제

• 
• 시간 제한: 2초
• 메모리 제한: 128MB

Problem Analysis

Naive 하게 풀면, 매번 각 순서를 정렬하여 답을 구할 수 있다. 이러한 방법은 시간 복잡도 차원에서 큰 부담이 된다. 대신에, 논리적으로 생각했을 때, 어떤 행동을 취할 때 상자에 계속 존재하는 사탕들을 매번 새롭게 정렬해 줄 필요는 없다. 이를 구현하기 위해, Segment Tree를 활용하면, 각 사탕의 개수를 저장하여, 구간에 존재하는 사탕의 개수를 통해, x번째 순위의 사탕을 찾을 수 있을 것이다.

Algorithm

Segment Tree를 이용해서, 사탕의 맛이 1인 것부터 1,000,000인 것까지의 각 개수를 저장한다

• update: x 맛 사탕의 개수를 수정
• getCandyNum: 왼쪽 구간과, 오른쪽 구간에 존재하는 사탕의 개수를 확인해서, x 번째로 맛있는 사탕이 존재할 수 있는 구간으로 recursive call을 하여, 해당 사탕의 맛 번호를 출력한다.

Data Structure

• Segment Tree[]: 1부터 1,000,000까지의 맛을 저장하기 위함

결과

Other

사탕의 맛 종류를 L = 1,000,000이라고 할 때, 시간 복잡도는 O(NlogL)이다.