백준 15501번 부당한 퍼즐

문제 링크입니다: https://www.acmicpc.net/problem/15501

STL 벡터에 친숙한 사람들은 모두 풀 수 있는 문제였습니다.

알고리즘은 아래와 같습니다.

1. 두 번째 배열을 입력 받을 때 첫 번째 배열의 시작 인덱스에 있는 숫자와 같은 숫자가 배치된 인덱스를 찾습니다.

2. 1번에서 찾은 인덱스로부터 첫 번째 배열과 동일한지 파악합니다.

-> 일치하면 "good puzzle" 출력

3. 2번에서 동일하지 않았다면 두 번째 배열을 뒤집은 다음에 2번을 다시 시도합니다.

-> 그래도 일치하지 않으면 "bad puzzle" 출력

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

 

const int MAX = 1000000;

 

int N;

vector<int> arr;

vector<int> input;

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0); //cin 실행속도 향상

        cin >> N;

 

        arr.resize(N);

        input.resize(N);

 

        for (int i = 0; i < N; i++)

                 cin >> arr[i];

 

        int startIdx;

        for (int i = 0; i < N; i++)

        {

                 cin >> input[i];

                 if (input[i] == arr[0])

                         startIdx = i;

        }

       

        //뒤집지 않은 상태에서 환형으로 봤을 때 현재 배열과 동일한지 파악

        bool same = true;

        for(int i=0; i<N; i++)

                 if (arr[i] != input[(startIdx + i) % N])

                 {

                         same = false;

                         break;

                 }

 

        if (same)

                 cout << "good puzzle\n";

        else

        {

                 //배열을 뒤집는다

                 reverse(input.begin(), input.end());

                 //시작 인덱스 재설정

                 startIdx = (N - 1) - startIdx;

                 //또 다시 환형으로 봤을 때 현재 배열과 동일한지 파악

                 same = true;

                 for(int i=0; i<N; i++)

                         if (arr[i] != input[(startIdx + i) % N])

                         {

                                 same = false;

                                 break;

                         }

                 if (same)

                         cout << "good puzzle\n";

                 else

                         cout << "bad puzzle\n";

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~