구간 트리. [1517]

[1. 문제 설명]

 

1	1	2	3	5	정렬 된 상태
3	2	1	5	1	최초 상태
2	3	1	5	1	3, 2 swap
2	1	3	5	1	3, 1 swap
2	1	3	1	5	5, 1 swap
1	2	3	1	5	2, 1 swap
1	2	1	3	5	3, 1 swap
1	1	2	3	5	2, 1 swap

3 이 3번의 swap 을 유도하고,

5 가 1번의 swap

2 가 2번의 swap

 

총 6번의 swap 이 발생하였다.

---

[2. 풀이 접근]

이해가 된 부분 까지만 정리 하도록

 

swap 의 주체는 인접한 두 값 중 큰 값 이다.

예를들어, 3 과 2 의 swap 이 발생 했을 때,

3 입장에서 한번 swap,

2 입장에서 한번 swap, 총 2번의 swap 이 발생과 같은 중복 처리는 있어선 안된다.

 

3 이 2 를 swap 하는 것이고,

2 는 3에 의해 swap 되는 것이다.

 

즉, 작은 수는 큰 수에 의해 swap 된다.

 

원래 배열을 정렬 한 상태에서 시작한다.

단, 정렬 했을 때 각 값이 원래 배열에서 위치한 index 를 알아둘 필요가 있다.

 

원래 배열에서 각 구간에서 정렬 된 개수를 저장하는 구간 트리를 하나 만든다.

최초 구간 트리 내 모든 값은 0 이다.

(버블 정렬 시작 전, 정렬 된 개수는 0 개이므로)

 

최초 1 은 원래 배열에서 index: 2 이다.

index 2 이후로 정렬 된 개수는 0 개 이다.

index 2 가 정렬 되었다고 구간 트리를 업데이트 한다.

 

그 다음 1 은 원래 배열에서 index: 4 이다.

index 4 이후로 정렬 된 개수는 0 개 이다.

index 4 가 졍렬 되었다고 구간 트리를 업데이트 한다.

 

그 다음 2 는 원래 배열에서 index: 1 이다.

index 1 이후로 정렬 된 개수는 총 2개이다.

index 1 이 정렬 되었다고 구간 트리를 업데이트 한다.

 

3 은 원래 배열에서 index: 1 이며, 이 이후로 정렬 된 개수는 총 3개 이다.

구간 트리 업데이트

 

5 는 원래 배열에서 index: 4 이며, 이 이후로 정렬 된 개수는 총 1개 이다.

구간 트리 업데이트

 

정렬 된 배열 순회를 완료하였다.

 

총 6번의 swap 이 발생하였음을 알 수 있다.

 

가장 작은 수 1 은 swap 의 주체가 아니므로, swap 수가 세어져서는 안된다.

최초 구간 트리 내 모든 노드의 값은 0 이므로 이러한 조건을 충족시킨다.

---

[3. 코드]