백준 1091 카드 섞기

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

public class Shuffle_cards {
    public static void main(String[] args) throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(in.readLine());
        int[] p = new int[N];
        int[] order = new int[N];
        HashSet<Integer> hash1 = new HashSet<>();
        HashSet<Integer> hash2 = new HashSet<>();
        HashSet<Integer> hash3 = new HashSet<>();
        int[] cards = new int[N];
        int[] init = new int[N];
        StringTokenizer st = new StringTokenizer(in.readLine());
        for (int i = 0; i < N; i++) {
            p[i] = Integer.parseInt(st.nextToken());
            cards[i] = i;//초기 카드 놓인 순서
            init[i]=i%3;
        }

        st = new StringTokenizer(in.readLine());
        for (int i = 0; i < N; i++) {
            order[i] = Integer.parseInt(st.nextToken());// 카드 섞는순서
        }
        if(Arrays.equals(init,p)) {// 섞을 필요있는지, 없다면 0
            System.out.println(0);
            return;
        }
        int playernum = 0;
        for (int i = 0; i < N; i++) { // 최종적으로 카드가 이렇게 놓여져 있으면 끝.
            for (int j = 0; j < N; j++) {
                if(p[j]==playernum){
                    if(playernum==0)
                        hash1.add(j);
                    else if(playernum==1)
                        hash2.add(j);
                    else
                        hash3.add(j);
                    p[j] = -1;
                    playernum = (playernum+1)%3;
                    break;
                }
            }
        }
        int result = 0;
        int [] next = new int[N];
        int[] compare = cards.clone();
        HashSet<Integer> h1 = new HashSet<>();
        HashSet<Integer> h2 = new HashSet<>();
        HashSet<Integer> h3 = new HashSet<>();
        while (true) {
            if (result != 0 && Arrays.equals(cards, compare)){
                System.out.println(-1);
                return;
            }
            h1.clear();
            h2.clear();
            h3.clear();
            for (int i = 0; i < N; i++) {
                next[order[i]] = cards[i];
            }
            for (int i = 0; i < N; i++) {
                if(i%3==0)
                    h1.add(next[i]);
                else if(i%3==1)
                    h2.add(next[i]);
                else
                    h3.add(next[i]);
            }
            cards = next.clone();
            result++;
            if(h1.equals(hash1)&&h2.equals(hash2)&&h3.equals(hash3))
                break;
        }
        System.out.println(result);
    }


}

풀이방법

🔉 주의할점 주는 순서가 달라도 결과적으로 플레이어가 받은카드의 결과가 같으면 되기 때문에, 순서를 상관하지 않는 hashSet을 사용한다.

1. 로직전, 어떤 플레이어에게 가야하는지를 나타내는 p와 init이 같다면, 섞을 필요가 없다는 뜻이므로 0을 출력후 함수를 빠져나온다.
2. p를 토대로 player 1,2,3에게(hash 1,2,3) 카드를 분배한다.
   hash1,2,3에는 최종적으로 player가 받아야하는 카드를 나타낸다.
3. 섞어도 섞어도(결국 처음 카드배열형태가 되는 순간이 온다.) 즉, 처음 카드 배열 형태가 왔는데도 while문을 탈출하지 못했다면 영원히 나오지 않는 결과이기때문에 -1을 출력한다.
4. order 순서에 따라 cards를 재배치 하고, 섞은 횟수 result를 증가 시킨다. 📢이 한줄이 풀이의 핵심이다.
5. 재배치한 카드를 h1,h2,h3(player1,2,3)에게 나눠준다.
6. h1,2,3이 hash1,2,3와 같다면 반복문을 탈출하고, 아니면 또 섞는다.

후기

처음에 보고 일단 문제가 무슨소린지 이해가 안됐다. 감도 안잡혀서
풀이를 봤는데 그사람은 카드를 안나눠주고 푸는 풀이었는데, 그런 방식이 일단 이해가 안됐다.
그래서 내방식대로 카드를 나눠주는 로직을 작성했고, 처음에 while문 안에서 hashset을 생성해서그런가 메모리 초과가 나왔다.
밖에서 선언해주고 clear()메서드 사용으로 변경했다.
배열의 clone()메서드, Arrays.equals(a,b)메서드를 새로 알게 되었다.
매우매우 유용하게 쓰일거 같다.