[백준] 1091 카드 섞기 자바 풀이

문제

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율

2 초

128 MB

2792

1210

897

47.335%

문제

지민이는 카지노의 딜러이고, 지금 3명의 플레이어(0, 1, 2)가 있다. 이 게임은 N개의 카드를 이용한다. (0 ~ N-1번)

일단 지민이는 카드를 몇 번 섞은 다음에, 그것을 플레이어들에게 나누어 준다. 0번째 위치에 있던 카드가 플레이어 0에게 가고, 1번째 위치에 있던 카드는 플레이어 1에게 가고, 2번째 위치에 있던 카드는 플레이어 2에게 가고, 3번째 위치에 있던 카드는 플레이어 0에게 가고, 이런식으로 카드를 나누어 준다. 하지만, 지민이는 약간 사기를 치려고 한다.

지민이는 처음에 카드를 섞기 전에 카드의 순서를 알고 있고, 이 정보를 이용해 각 카드가 특정한 플레이어에게 보내지게 할 것이다.

카드를 한 번 섞을 때는 주어진 방법을 이용해서만 섞을 수 있고, 이 방법은 길이가 N인 수열 S로 주어진다. 카드를 한 번 섞고 나면 i번째 위치에 있던 카드는 S[i]번째 위치로 이동하게 된다.

각 카드가 어떤 플레이어에게 가야 하는지에 대한 정보는 길이가 N인 수열 P로 주어진다. 맨 처음 i번째 위치에 있던 카드를 최종적으로 플레이어 P[i] 에게 보내야한다.

지민이가 목적을 달성하기 위해 필요한 카드 섞는 횟수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. N은 3보다 크거나 같고, 48보다 작거나 같은 3의 배수이다.

둘째 줄에 길이가 N인 수열 P가 주어진다. 수열 P에 있는 수는 0, 1, 2 중 하나이다.

셋째 줄에 길이가 N인 수열 S가 주어진다. 수열 S에 있는 수는 모두 N-1보다 작거나 같은 자연수 또는 0이고 중복되지 않는다.

출력

첫째 줄에 몇 번 섞어야 하는지 출력한다. 만약, 섞어도 섞어도 카드를 해당하는 플레이어에게 줄 수 없다면, -1을 출력한다.

풀이

가장 중요한 것은 섞어도 카드를 해당하는 플레이어에게 줄 수 없는 경우를 구하는 것인데, 나 같은 경우 섞다가 맨 처음 형태와 같은 형태가 나온다면 (싸이클이 있다면) 원하는 플레이어 에게 줄 수 없다고 생각했다.

따라서 아래와 같이 반복 계산 해줬다.

1. 한번이라도 섞고 난 이후에 처음 형태와 같아졌을 경우 반복을 종료하고 -1 리턴
2. 0,1,2 순서대로 잘 섞여졌다면 반복을 종료
3. 카드 섞기
4. 섞은 수 올려주기

문제를 제대로 못 읽어서 N, S를 거꾸로 생각하는 바람에 많은 시간을 사용했다.

코드

package com.company.baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class B1091 {
    static int N;
    static int[] P;
    static int[] S;
    static int[] origin;
    static int[] tmp;
    static int cnt;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());

        P = new int[N];
        origin = new int[N];
        tmp = new int[N];
        S = new int[N];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            P[i] = Integer.parseInt(st.nextToken());
            origin[i] = P[i];
        }

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            S[i] = Integer.parseInt(st.nextToken());
        }
        
        while (true) {
            if (cnt > 0 && isEqual()) {
                cnt = -1;
                break;
            }
            if (isStop()) {
                break;
            }
            swap();
            cnt++;
        }
        System.out.println(cnt);
    }
    public static boolean isEqual() {
        for (int i = 0; i < N; i++) {
            if (tmp[i] != origin[i]) return false;
        }
        return true;
    }
    public static boolean isStop() {
        for (int i = 0; i < N; i++) {
            if (P[i] != i % 3) return false;
        }
        return true;
    }
    public static void swap() {
        for (int i = 0; i < N; i++) {
            tmp[S[i]] = P[i];
        }
        P = Arrays.copyOf(tmp, tmp.length);
    }
}