[ 백준 BOJ ] 1091번 - 카드 섞기 (C++)

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

 

생각 흐름

• S에 맞게 계속적으로 반복문을 돌면서 만약 기존에 같은 형식이 나오면 -1을 반환하고, P와 같은 꼴이 나오면 반복 횟수를 반환해주면 되는 간단한 구현 문제이다.

 

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <memory.h>

using namespace std;

int N;
vector<int> P;
vector<int> S;
unordered_map<string,bool> um;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin>>N;
    
    int tmp;
    for(int i = 0; i<N; i++){
        cin>>tmp;
        
        P.push_back(tmp);
    }
    
    for(int i = 0; i<N; i++){
        cin>>tmp;
        
        S.push_back(tmp);
    }
    
    vector<int> init;
    for(int i = 0; i<N; i++){
        init.push_back(i);
    }
    
    int answer = -1;
    
    while(true){
        string tmp = "";
        
        for(int i = 0; i<N; i++){
            tmp += to_string(init[i]);
            tmp+=" ";
        }
        
        if(um[tmp]) {
            cout<<-1<<endl;
            return 0;
        }
        
        answer++;
        
        bool isSame = true;
        for(int i = 0; i<N; i++){
            if(P[init[i]]!=i%3) {
                isSame = false;
                break;
            }
        }
        
        if(isSame) break;
        
        um[tmp] = true;
        
        vector<int> next = init;
        
        for(int i = 0 ; i<N; i++){
            next[S[i]] = init[i];
        }
        
        init = next;
        
    }
    
    cout<<answer<<endl;
    
    return 0;
}