[알고리즘] 카드 섞기 (백준 1091번)

1091번: 카드 섞기

 문제가 좀 헷갈리긴 하는데 푸는 것 자체는 어렵지 않다. 다만 섞어도 절대 P와 같은 케이스를 만들 수 없는 경우의 수를 찾는 게 핵심인데 한 마디로 사이클을 찾으라는 뜻이다.

 

Solution

 매 반복문마다 S[i] 순서에 맞춰서 i번째 위치에 있는 카드를 S[i]번 위치로 옮기면 된다. 이 때 S[i]번째 위치로 옮긴다는 의미는 S[i]번 카드를 가지고 있는 사람이 이젠 i번 카드를 가지고 있다는 의미가 된다.

		while(!Arrays.equals(card, P))
		{
			int temp[] = card.clone();

			//i번째 위치의 카드를 S[i] 위치로
			for(int i = 0;i < N;i++)
				card[i] = temp[S[i]];

			//이미 존재하는 조합 -> 사이클 존재 -> 절대 못구함
			if(count > 120119)
			{
				bw.write("-1");
				return;
			}

			count++;
		}

 해당 부분의 코드인데 처음에는 사이클이 있는지 파악하기 위해 HashSet을 이용하여 String 형으로 card 조합을 저장해뒀다가 중복된 조합이 발생하면 "-1"을 출력하도록 했다. 그렇게 해도 문제는 풀리는데 시간은 엄청 오래 걸린다.

 다른 코드를 보던 중 사이클이 발생하는 경우는 120120번 이상 섞으면 발생한다고 한다. 아마 최대로 나올 수 있는 조합이 120119개라서 그런 것 같다.

 

 전체 코드이다

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main {

	static int S[], P[], card[];
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

	public static void solution() throws Exception
	{
		int N = Integer.parseInt(br.readLine());

		S = new int[N];
		P = new int[N];
		card = new int[N];

		String[] list = br.readLine().split(" ");

		for(int i = 0;i < N;i++)
		{
			P[i] = Integer.parseInt(list[i]);
			card[i] = i % 3;
		}


		list = br.readLine().split(" ");

		for(int i = 0;i < N;i++)
			S[i] = Integer.parseInt(list[i]);

		int count = 0;

		while(!Arrays.equals(card, P))
		{
			int temp[] = card.clone();

			//i번째 위치의 카드를 S[i] 위치로
			for(int i = 0;i < N;i++)
				card[i] = temp[S[i]];

			//이미 존재하는 조합 -> 사이클 존재 -> 절대 못구함
			if(count > 120119)
			{
				bw.write("-1");
				return;
			}

			count++;
		}

		bw.write(count+"");
	}


	public static void main(String[] args) {
		try
		{
			solution();

			bw.close();
			br.close();
		}
		catch (Exception e)
		{
			e.printStackTrace();
		}
	}

}