[백준 1091] 카드 섞기 - JAVA

BOJ Link

https://www.acmicpc.net/problem/1091

 

 

풀이 과정

단순 구현 문제이며 시간은 널널하다.

다소 이해가 힘든 문제를 파악하고, 카드를 섞는 방법을 코드로 표현하는 것에 중점을 둔 문제같다.

 

origin, next, now, goal, suffle 5개의 배열을 사용한다. cnt는 카드를 섞은 횟수이다.

 

origin - 초기 카드 상태

next - 카드를 섞은 이후 카드 상태

now - 현재 카드 상태

goal - 목표 카드 상태

suffle - 카드를 섞는 패턴

 

각 배열의 초기화 이후, 다음과 같은 과정을 반복한다.

 

1. goal과 now를 비교하여 같다면 cnt 출력

 

2. cnt != 0이고, origin과 now를 비교하여 같다면 -1 출력

(한 싸이클을 돌고나서도 초기 상태와 같아진다면 정답이 될 수 없다.)

 

3. suffle 배열에 따라 now를 섞어 next에 저장한 후, now를 next로 덮어씌움

 

4. cnt 1증가

 

 

핵심은 다음과 같다.

 

1. 목표를 달성해야할 수열 goal은 3보다 작은 값 [0-2]만 다루므로, 0~N-1의 값을 mod 3하여 사용한다.

=> 해당 카드가 몇 번째 카드인지는 알 필요 없다. 어떤 플레이어에게 나누어 줄 카드인지만 알면 된다.

 

2. 카드를 섞는 방법

=> next의 i번째에 now의 suffle[i]번째 카드가 와야한다.

next[i] = now[suffle[i]];

 

제출 코드

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

class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int mod = 3;
        int cnt = 0;

        int[] next = new int[N];
        int[] origin = new int[N];
        int[] now = new int[N];
        int[] suffle;
        int[] goal;

        for (int i = 0; i < N; i++) {
            int v = i % mod;
            origin[i] = v;
            now[i] = v;
        }

        goal = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        suffle = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        while (true) {
            if (isSame(now, goal, N)) {
                break;
            }
            if (cnt != 0 && isSame(origin, now, N)) {
                cnt = -1;
                break;
            }

            for (int i = 0; i < N; i++) {
                next[i] = now[suffle[i]];
            }

            for (int i = 0; i < N; i++) {
                now[i] = next[i];
            }

            cnt++;
        }

        System.out.println(cnt);
    }

    static boolean isSame(int[] a, int[] b, int N) {

        for (int i = 0; i < N; i++) {
            if (a[i] != b[i]) return false;
        }

        return true;
    }
}