Sorting Game _ 알고스팟 _ 종만북

https://algospot.com/judge/problem/read/SORTGAME

algospot.com :: SORTGAME

 조건

1) 테스트케이스 (1 ~1000)

2) 수열의 길이 (1 ~ 8)

3) 한 수열에 두가지 이상의 수가 출현하지 않는다.

 

 

 1. 풀이 방법

 1) 그냥 완전탐색으로 풀면 왜 안되는가?

 

 이 문제를 그냥 전체를 탐색하며 풀게되면 하나당 최악의 경우 8!개의 정점을 탐색하게 되므로 여러개의 테스트케이스가 있는 이 문제 특성상 시간안에 풀기는 어렵다. 

 

 2) 그렇다면 해결방법은?

 

  조건중 3)을 주의깊게 살펴보면 수열의 크기가 다 다르다. 그러므로 수열 안의 상대적인 거리 순서대로 수열안의 값을 바꿔보자 ( 순서는 0부터 시작 ) 

 

(22, 30, 15, 45) -> (1, 2, 0, 3) 

 

 이 두 수열은 정렬하기 위해 뒤집는 횟수가 같다.  그러므로 모든 8자리의 수열이 몇번뒤집어서 정렬이되는지에 대한 

모든 케이스들을 미리 만들어놓는다면 테스트케이스가 1000개이던 1개이던 8!만큼만 탐색해도 될것이다.

 

 8자리 수열에 모든 케이스를 만들어도 테스트케이스가 4자리, 5자리 이렇게 자릿수가 다를수있다.

 이때를 대비해서 상대적인 거리 순서대로 바꿀때 8자리에서 부족한 자릿수만큼 뒤를 채워준다면 4자리 혹은 5자리라도 답을 알아낼수 있을것이다.

 

ex ) (22, 30, 15, 45) -> (1, 2, 0, 3) + (4, 5, 6, 7) = (1, 2, 0, 3, 4, 5, 6, 7)

 

 

 

 2. 코드

 

#include <iostream>
#include<algorithm>
#include <vector>
#include <map>
#include <queue>

#define MAXN 8

using namespace std;

map<vector<int>, int> sorted;

void makeSorted(int n)
{
	//0,1,2,3,4,5,6,7
	vector<int> pr;
	queue <pair<vector<int>, int>> que;
	for (int i = 0; i < n; i++)
		pr.push_back(i);

	sorted.insert(make_pair(pr, 0));
	que.push(make_pair(pr, 0));

	while (!que.empty())
	{
		vector<int> qpr = que.front().first;
		int cnt = que.front().second;
		for (int i = 0; i < n - 1; i++)
		{
			for (int j = i + 2; j <= n; j++)
			{
				reverse(begin(qpr) + i, begin(qpr) + j);
				if (sorted.count(qpr) == 0)
				{
					sorted.insert(make_pair(qpr, cnt + 1));
					que.push(make_pair(qpr, cnt + 1));
				}
				reverse(begin(qpr) + i, begin(qpr) + j);
			}
		}
		que.pop();
	}
}

int solve(vector<int> pr)
{
	vector<int> changepr;

	for (int i = 0; i < (int)pr.size(); i++)
	{
		int small = 0;
		for (int j = 0; j < (int)pr.size(); j++)
		{
			if (pr[i] > pr[j])
				small++;
		}
		changepr.push_back(small);
	}

	//나머지 부분들도 넣기
	if (changepr.size() < MAXN)
	{
		for (int i = changepr.size(); i < MAXN; i++)
			changepr.push_back(i);
	}

	return sorted[changepr];
}

int main()
{
	makeSorted(MAXN);
	
	int testcase;
	cin >> testcase;
	for (int i = 0; i < testcase; i++)
	{
		int n;
		cin >> n;
		vector<int> pr;
		int value;
		for (int j = 0; j < n; j++)
		{
			cin >> value;
			pr.push_back(value);
		}

		cout << solve(pr) << '\n';
	}

	return 0;
}

 

 

 

 

 3. 후기 

종만북 어렵다.