8568

static int N;
static int permu[1000];

static int solution(void)
{
	int tmp, ret = 0;
	list<int> cache[3][3]; //해당 위치에서 필요한 나머지, 실제 나머지, 값의 위치

	scanf("%d", &N);
	for (int i = 1; i <= N; i++)
	{
		scanf("%d", &permu[i]);
		tmp = permu[i] % 3; //해당 값의 나머지,

		if (tmp == i % 3)
			permu[i] = -1; //고정됨,
		else
			cache[i % 3][tmp].push_back(i);
	}

	for (int i = 1; i <= N; i++)
	{
		if (permu[i] == -1)
			continue;

		int needs = i % 3, rem = permu[i] % 3;

		if (cache[rem][needs].size()) //서로 교환할 수 있으면,
		{
			int j = cache[rem][needs].front();
			permu[j] = -1;
			cache[rem][needs].pop_front();
		}
		else
		{
			int idx;
			//필요한 나머지를 갖고 있는 곳을 탐색,
			for (idx = 0; idx < 3 && cache[idx][needs].empty(); idx++); 
			int j = cache[idx][needs].front();

			cache[idx][needs].pop_front();
			permu[j] = permu[i]; //i번째 값을 옮김,
			cache[j % 3][rem].push_front(j); //옮겨진 위치를 저장,
		}

		/*else문에서 옮겨진 위치의 순서가 정렬되지 않아서 탐색해서 제거해야함*/
		cache[needs][rem].remove(i); 
		permu[i] = -1;
		ret += 1; //교환 횟수 증가,
	}

	return ret;
}

아래의 예시로 위 코드의 동작방식을 정리하겠다.

1	2	0	1	2	0	1	2	0
6	(8)	2	9	3	7	(1)	(5)	4
0	2	2	0	0	1	1	2	1

첫번째 행은 해당 위치에 와야할 나머지 값,

두번째 행은 입력으로 주어지는 값,

마지막 행은 해당 값의 나머지 값이다.

 

위 표에서 괄호쳐진 곳만 맞는 자리에 온 것이다.

 

먼저 6은 7과 교환되어야 한다. 

그 이유는 6이 있는 자리에서는 나머지가 1이 되는 수가 와야 되고,

7이 있는 자리에서는 나머지가 0이되는 수가 와야 되기 때문이다.

 

이런 식으로 제자리에 오지 않은 값에 대해서는 리스트 cache에서 적절한 위치를 가져올 수 있다.

그러나 위 경우처럼 서로 교환 되어 언제나 두 값이 제자리를 갖지 못하는 경우가 있다.

 

3 1 2 의 경우가 바로 그것이다.

이 경우는 먼저 앞선 인덱스 부터 제자리를 맞추는 식으로 했다.

교환되는 숫자의 위치와 관계없이 해당 위치의 값의 나머지가 현재 위치에서 필요한 값이라면 

일단 교환을 하는 것이다.

 

3 1 2 -> 1 3 2 가 되는 것이다.

그리고 이 경우 첫번째 인덱스에 있던 3은 아직 유효하므로 제거 되지 않아야 한다.