[1517] 버블 소트

https://www.acmicpc.net/problem/1517

1517번: 버블 소트

제목은 버블 소트지만 크게 세그먼트트리 또는 머지 소트로 접근하는 문제다. 세그먼트 트리를 공부하기 위해 세그먼트 트리로 접근했다.

 

풀이

버블 소트는 자신보다 뒷순번의 숫자 중 더 작은 숫자와 swap이 일어나게 된다. 즉 자신보다 뒷순번의 숫자 중 더 작은 수의 개수를 세그먼트 트리를 통해 구해내고 그 수의 합을 반환하면 문제에서 요구하는 swap이 일어나는 수를 구할 수 있다는 얘기다.

 

입력된 수열에 숫자와 인덱스가 담긴 튜플배열을 생성하여 숫자 기준 오름차순으로 정렬한다. 0으로 초기화된 세그먼트트리를 생성. 이후 (숫자, 인덱스) 튜플이 담긴 배열을 순회하면서 (인덱스 ~ N-1) 구간의 숫자를 정답에 더해준 뒤 해당 구간에 +1 갱신해 준다. 수열을 모두 돌게 되면 자연스럽게 자신보다 뒷구간에 더 작은 숫자들의 개수를 계산할 수 있게 된다.

 

예제 [3,2,1]을 기준으로 설명하면 다음과 같다.

구간 합 세그먼트 트리 생성. (숫자, 인덱스) 튜플을 숫자 기준 오름차순으로 정렬한다.

 

1의 인덱스는 2였다. 2부터 마지막 인덱스 2 즉 2~2 구간의 값을 조회. 0을 정답에 추가.

이후 들어올 구간합을 계산하기 위해 2-2에 +1 갱신작업을 한다.

 

다음 숫자의 인덱스는 1이다. 1~2구간의 값을 조회. 1이 반환되며 해당 결과를 정답에 저장. 

이후 마찬가지로 1-1 구간에 +1 갱신 작업을 한다.

 

마지막 3의 인덱스는 0이다. 0~2 구간의 값을 조회. 3보다 뒤에 있으면서 작은 숫자들의 개수는 2이다. 정답에 저장한다.

0-0 구간에 +1 갱신. 정답에는 0 + 1 + 2 즉 3이 담겨있고 해당 값이 swap이 일어난 횟수이다.

 

정답 코드