구간 트리. [1168]

[1. 문제 설명]

1 부터 N 까지 나열 된 원이 있을 때,

순서대로 K 번째 값을 제거 했을 때

제거되는 순서를 출력한다.

[2. 풀이 접근]

기본적인 전략은 아래 문제와 동일하다.

간단히 다시 정리하면

구간에 속한 원소의 개수를 알 수 있으므로,

logN 시간복잡도로 남아 있는 수열에서 k 번째 숫자를 찾는 것이다.

여기서 문제는 수열이 원형 형태라는 것이다.

예제 입력을 토대로 동작 방식을 살펴보면,

(N=7, K=3)

▼

[1][2][3][4][5][6][7]

▼

[1][2][4][5][6][7] # 이전 위치를 기준으로 3번째 원소

▼

[1][2][4][5][7] # [1][2][4][5][6][7][1][2][4][5][7] => 원형 형태 수열이므로 이런 구조라고 볼 수 있다.

# 6에서 3칸 뒤로 가면 2가 된다.
▼

[1][4][5][7]

▼

[1][4][5] # [1][4][5][7][1][4][5]

# 7에서 3칸 뒤로 가면 5가 된다.

▼

[1][4] # [1][4][5][1][4][1][4]...

# 5에서 3칸 뒤로 가면 1이 된다. # 5는 삭제되므로 [1][4] 다음에 5가 올 수 없다.

[4]

위 과정을 통해서 한가지 알 수 있는 점은 삭제된 위치를 기준으로 3칸 뒤로 이동한 것이

구간이 갖는 원소 개수를 넘어간 경우 다시 구간의 앞으로 이동한 것으로 볼 수 있다는 것이다.

즉, 원형 큐와 처럼 수열의 길이를 초과한 경우

수열의 길이로 나눈 나머지를 이용하여 가리키는 곳을 다시 수열의 앞쪽으로 이동 시킬 수 있다.

여기서 한가지 유의할 점은 위에서 계산 한 값이 0 이 되는 경우이다.

이 경우는 k 를 남은 수열의 개수로 처리하면 된다.

mod 연산을 하기 전 k 가 수열의 개수 였기 때문이다.

[3. 코드]

test_kernelv2