개요

백준 3006번: 터보소트

• 입력
  첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이며, 배열의 크기이다.

  둘째 줄부터 N개의 줄에는 1보다 크거나 같고, N보다 작거나 같은 수가 중복 없이 주어진다. 이 숫자가 차례대로 배열에 포함되어 있는 수이다.

• 출력
  각 단계에서 숫자의 위치를 몇 번 바꾸는지 출력한다. 총 N줄을 출력해야 한다.

접근방식

1. 처음엔 가장 긴 증가하는 부분수열 느낌으로
   값들을 정렬한 후, 0부터 각 값의 인덱스까지의 가장 긴 증가하는 부분 수열값을 해당 인덱스에서 빼줌으로써 해당값보다 작은값이 몇개 있는지 체크하려했다.
   하지만 문제에서 해당 값은 자기자리로 간다고 했으므로 해당 값을 연산 후에 제거해야하는데 그 방법을 어떻게 적용해야할지 모르겠어서 검색했다.

2. 찾아본 아이디어는 정렬한 다음 1, N, 2, N-2순서로 방문하면서
   해당 구간 내에 1로 초기화되어있는 구간합배열을 사용하면 깔끔하게 풀리는 것이였다.

3. 방문하며 원하는 구간의 구간합을 구하면 해당 구간에 몇개의 원소가 들어있는지 나올 것이며, 제일 모르겠었던 자기자리 찾아간 해당 원소를 제거하는 부분은 해당 인덱스의 값을 0 처리해버리면 되는 것이였다!

4. 하지만 1로 초기화된 배열을 사용하다보니 생긴 문제인데
   제자리에 잘 있는 값을 대상으로 연산할 때 target구간의 양 값이 같아서 초기화 되어있는 1을 불러와 1칸 움직이게 만들어버린다.

5. 따라서 더 검색해본 결과, 처음 리프노드를 0으로 초기화 한 후,
   변경이 생겨 이동한 원소를 1로 바꿔주는 방식으로 푸는 방식이 쉬웠다.

6. 이렇게 0에서 1로 바꿔주면서 세그먼트 트리를 구간합트리로 이용하게 되면, 이제 해당 구간에서의 세그먼트 트리값을 제자리로 찾아간 원소의 갯수로 운용할수 있게 된다.
   따라서 (원래 인덱스값에서 0이나 N-1까지의 거리) - (세그먼트 트리값) 이 이동하는 거리가 된다.

   for (int i = 0; i < N; i++) {
   		int pos;
   		//홀수일 때 제일 큰수 고르기(0부터 시작이라 반대임)
   		if (i % 2) {
   			//홀수값 다음 홀수값일때 이 조건문 안으로 들어온다 \
   			 따라서 조건문 안으로 들어오는 i값이 2씩 차이나므로 우리가 원하는 인덱스 가져오려면 2로 나눠서 1씩 차이나게 변형해야함 
   			pos = GreaterVec[N-1-i/2].second;
   			//끝값 인덱스 N-1에서 현재 인덱스값과 이미 자기자리 찾아간 숫자갯수 빼줘서 이동해야하는 숫자 구함
   			cout << N - 1 - pos - HowManyNumsInTargetRange( pos,N-1, 1, 0, firstLeafNodeIdx - 1)<<'\n';
   		}
   		//짝수일 때 제일 작은 수 고르기
   		else {
   			//위의 주석과 같이 짝수일때 이 조건문 안으로 들어오므로 i값이 2씩 차이난다. \
   			2로 나눠서 원하는 인덱스로 변형
   			pos = GreaterVec[i/2].second;
   			//해당 인덱스에서 자기자리 찾아간 숫자갯수 빼줌
   			cout << pos-HowManyNumsInTargetRange(0,pos,1,0,firstLeafNodeIdx-1)<<'\n';
   		}
   		//자기자리 찾아간 상태이므로 구간합트리의 조상노드들 전부 1씩더하며 갱신해줌
   		SetAncestorNode(pos);
   	}

7. 처음엔 이게 이해가 안 되었다.
   제자리를 찾아갔다면 찾아간 자리의 값을 1 증가시켜야지
   왜 찾아가기 전의 값을 1 증가시키는지 이해가 안 되었다.

8. 예시로 들어보면
   7
   4 6 5 3 2 1 7
   이렇게 입력값이 들어왔을 때,

이런 상황이고, 값에 따라 정렬해보면

초기 상태로는 이렇게 되어있다.

그 후 첫번째 값을 원 위치로 이동시키면 5만큼 이동하고
(인덱스(5) - [0,5]구간에서 값 1인 리프 노드 갯수(0)) 해서 5가 출력된다.

그 다음 N번째 값은 인덱스 6에 있으므로

그 다음 N번째 값을 원위치로 이동시키려보니 원래 자리에 잘 있다.
(N-1 (6) - 인덱스 (6) - [6,6]구간에서 값 1인 리프노드 갯수(0)) 해서 0출력된다.

하지만 그다음 값인 2를 다룰때

2의 인덱스는 4이므로 인덱스 4에서 1까지 3만큼 이동해야 한다고 생각을 했다.
하지만 위에 작성한 코드대로라면
(인덱스 (4) - [0,4] 안에 값 1인 리프노드 갯수(0)) 해서 4만큼 이동한다.

그래서 왜일까 고민을 많이 했었다.
-> 정말 쉬운 이유였는데 1이 앞으로 이동하면서 2가 밀린것이였다.

처음 이 풀이를 봤을 땐 직관적으론 잘 이해가 안 되었다.
각 값마다 현재 인덱스에서
0또는 N-1값까지의 거리 - 해당 구간에서 제자리로 찾아간 수의 갯수를 빼주면 작동이 되는 것이였다.

더 생각을 해본 결과, 이렇게 혼자 정리를 할 수 있었다.

이미 값을 기준으로 정렬이 된 상태이다.

• 현재 값을 N이라 해보자.
  홀수번째 기준으로 [0, N의 인덱스]의 구간에서
  이미 제자리를 찾아간 아이들은 N보다 작은 값들이다.

N을 판단할 차례일때, 이미 N보다 작은 값들은 제자리를 찾은 상태이고, 세그먼트트리에서 자신의 리프노드 값이 1로 변경되어 있다.

따라서 (N의 인덱스 - [0, N의 인덱스]구간에서 세그먼트트리값이 1인 값들의 갯수)가 결국 N이 제자리를 찾으러 가기위한 이동 횟수다.

N보다 작은 수가 N보다 뒤쪽 인덱스에 있을 땐 어떡하냐라는
궁금증이 들 수 있는데 N보다 뒤의 값이 제자리 찾아가면 그만큼
다른 수들을 뒤로 밀면서 앞으로 가게 되므로 상관이 없다.
결국 (N의 인덱스 - [0, N의 인덱스]구간에서 세그먼트 트리값이 1인 갯수)가 답이 되는건 똑같다.

전체코드

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;
int SegTree[262144];

vector<pair<int, int>> GreaterVec;

int N,tmp=0,firstLeafNodeIdx=1;

bool Greater(pair<int, int> a,pair<int,int> b) {
	return a.first < b.first;
}

int HowManyNumsInTargetRange(int targetL, int targetR, int nodeNum, int curL, int curR) {
	if (curL > targetR || curR < targetL) return 0;
	if (targetL <= curL && curR <= targetR) return SegTree[nodeNum];
	int mid = (curL + curR) / 2;
	return HowManyNumsInTargetRange(targetL, targetR, nodeNum * 2, curL, mid)+
		HowManyNumsInTargetRange(targetL, targetR, nodeNum * 2+1, mid+1, curR);
}
void SetAncestorNode(int n) {
	int tmp = n + firstLeafNodeIdx;

	while (tmp > 1) {
		SegTree[tmp]++;
		tmp /= 2;
	}
}

void Solution() {
	for (int i = 0; i < N; i++) {
		int pos;
		//홀수일 때 제일 큰수 고르기(0부터 시작이라 반대임)
		if (i % 2) {
			//홀수값 다음 홀수값일때 이 조건문 안으로 들어온다 \
			 따라서 조건문 안으로 들어오는 i값이 2씩 차이나므로 우리가 원하는 인덱스 가져오려면 2로 나눠서 1씩 차이나게 변형해야함 
			pos = GreaterVec[N-1-i/2].second;
			//끝값 인덱스 N-1에서 현재 인덱스값과 이미 자기자리 찾아간 숫자갯수 빼줘서 이동해야하는 숫자 구함
			cout << N - 1 - pos - HowManyNumsInTargetRange( pos,N-1, 1, 0, firstLeafNodeIdx - 1)<<'\n';
		}
		//짝수일 때 제일 작은 수 고르기
		else {
			//위의 주석과 같이 짝수일때 이 조건문 안으로 들어오므로 i값이 2씩 차이난다. \
			2로 나눠서 원하는 인덱스로 변형
			pos = GreaterVec[i/2].second;
			//해당 인덱스에서 자기자리 찾아간 숫자갯수 빼줌
			cout << pos-HowManyNumsInTargetRange(0,pos,1,0,firstLeafNodeIdx-1)<<'\n';
		}
		//자기자리 찾아간 상태이므로 구간합트리의 조상노드들 전부 1씩더하며 갱신해줌
		SetAncestorNode(pos);
	}

}

void Input() {
	cin >> N;
	while (N > firstLeafNodeIdx) firstLeafNodeIdx *= 2;
	fill(SegTree, SegTree + 262144, 0);
	for (int i = 0; i < N; i++) {
		cin >> tmp;
		GreaterVec.push_back({ tmp, i });
	}
	sort(GreaterVec.begin(), GreaterVec.end(), Greater);
	Solution();
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	Input();
}

문풀후생

정말 쉽지 않았던 문제였던 것 같다.
자기자리 찾아간 수들을 1로 표시하고 해당 구간의 합을 통해
자기자리 찾아간 수들을 구한다는 개념이 정말 신선했다.