터보소트( BOJ 3006 )

문제

3006. 터보소트 : https://www.acmicpc.net/problem/3006

3006번: 터보소트

문제 파악하기

• 시작 부분과 종료 지점을 번갈아가면서 정렬을 할 때, 교환되는 횟수를 구하는 문제입니다.
• 버블 정렬을 기반으로 진행하기 때문에 현재 위치와 정렬되었을 때의 위치의 차이가 핵심요소가 될 수 있습니다.
• 현재 위치에서 원하는 위치까지 가는데 얼만큼 숫자를 교환해야 할까요?

 

문제 해결하기

• 정답은 세그먼트 트리를 이용하는 것입니다.
• 입력된 위치와 정렬했을 때의 위치를 이용하면 필요한 교환 횟수를 구항 수 있습니다.
• 우선 입력된 위치를 오름차순으로 정렬한 후, 정렬된 숫자들을 순서대로 입력된 위치에 삽입합니다.
• 그러면서 세그먼트 트리를 이용하여 현재 입력된 숫자의 개수를 세그먼트 트리로 카운트합니다.
• 카운트 된 숫자만큼은 교환에 해당되지 않는 숫자입니다. 즉, 현재 위치에서 시작 지점까지 0의 개수를 카운트합니다.
• 각각의 입력에 대해 0의 개수를 카운트하면 정답을 알 수 있습니다.

 

후기

세그먼트 트리와 정렬을 활용하는 기법은 널리 알려진 방법이라고 할 수 있습니다. 만약 이런 문제가 처음이라면 정보올림피아드의 줄 세우기 문제들을 풀어보길 추천합니다.