DAY4 고급 - 백준 2505번 (C++)

www.acmicpc.net/problem/2505

2505번: 두 번 뒤집기

 

<답안>

#include <iostream>
#include <iostream>
using namespace std;
void reverse(int array[], int left, int right)
{
    if(left < right)
    {
        swap(array[left],array[right]);
        reverse(array,left+1,right-1);
    }
}
int main()
{
    int n;
    int array[10001] = {0};
    int temp[10001] = {0};
    int left = -1,right = -1;
    int ResultLeft[2];
    int ResultRight[2];
    int count = 0;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>array[i];
        temp[i] = array[i];
    }

    for(int i=1; i<=n; i++)
    {
        //위치와 다른숫자의 시작 경우
        if(array[i] != i && left == -1)
        {
            left = i;
            ResultLeft[count] = i;
            continue;
        }
        else if(array[i] == left)
        {
            right = i;
            ResultRight[count] = i;
            count++;
            reverse(array,left,right);

            left = -1;
            right = -1;
            i = 1;
        }
    }

    if(count > 2)
    {
        count = 0;
        for(int i=n; i>0; i--)
        {
            //위치와 다른숫자의 시작 경우
            if(temp[i] != i && right == -1)
            {
                right = i;
                ResultRight[count] = i;
                continue;
            }
            else if(temp[i] == right)
            {
                left = i;
                ResultLeft[count] = i;
                count++;
                reverse(temp,left,right);

                right = -1;
                i = n;
            }
        }
    }
    if(count == 2)
    {
        cout<<ResultLeft[0]<<" "<<ResultRight[0]<<"\n";
        cout<<ResultLeft[1]<<" "<<ResultRight[1]<<"\n";
    }
    else if(count == 1)
    {
        cout<<ResultLeft[0]<<" "<<ResultRight[0]<<"\n";
        cout<<1<<" "<<1<<"\n";
    }

    else if(count == 0)
    {
        cout<<1<<" "<<1<<"\n";
        cout<<1<<" "<<1<<"\n";
    }

    return 0;
}

 

<설명>

이 문제는 규칙을 찾기만 하면 쉽게 풀리는 문제였다. 다만 그 규칙을 찾는거 자체가 좀 어려웠다 규칙은 이렇다

"

i=1부터 n까지 증가시키며

i번째 숫자가 i와 같은경우 다음숫자로 넘어가고

i번째 숫자가 i와 다른경우 i를 left로 저장, 그 다음 숫자부터 i와 같은 숫자를 찾아 그 위치를 right로 저장하여

left부터 right 까지의 숫자를 뒤집는다 (reverse)

뒤집고 나면 다시 i=1부터 확인한다

"

이렇게 하면 i번째의 숫자는 정상적으로 바뀌고, 그 뒤또한 정상이거나 비정상인 부분이 생기게 된다

 

ex) (6 7 8 2 1) 5 4 3 9 10 -> (1 2 8 7 6) 5 4 3 9 10 이렇게 바뀌게 된다

      left         right

->  1 2 (8 7 6 5 4 3) 9 10 -> 1 2 3 4 5 6 7 8 9 10 (완료)

            left            right

 

다만 여기서 한번 어려움을 겪었다

ex) 1 4 6 5 2 3 7 -> 1 (4 6 5 2) 3 7 -> 1 2 5 6 4 3 7 -> 1 2 (5 6 4 3) 7 -> 1 2 3 4 6 5 7
 -> 1 2 3 4 (6 5) 7 -> 1 2 3 4 5 6 7

 

이런 경우는 위 알고리즘 상으론 "3번" 뒤집어야 정상이 나오는 케이스였다

여기서 또 핵심 규칙을 찾아야 하는데 찾기만 하면 풀리는 문제다 그 규칙은 바로 "뒤에서부터 확인해보기" 이다

 

위 예제를 같은방법이지만 방향을 뒤에서부터 확인하는 식으로 다시 살펴보면

ex) 1 4 6 5 2 3 7 -> 1 4 (6 5 2 3) 7 -> 1 4 3 2 5 6 7 -> 1 (4 3 2) 5 6 7 -> 1 2 3 4 5 6 7

 

이렇게 정상적으로 2번뒤집기로 끝나게 된다!

 

그래서 정리를 하자면, array[10001]로 배열을 만든다음, i=1부터 n까지 증가시키며

숫자가 i와 다른경우 시작점을 left로 저장 (초기값인지 확인을 위해 if left == -1 과정을 넣었다)

숫자가 left와 같은경우 끝점으로 right로 저장 (left != -1 즉 left값이 있는 경우로 확인)

그렇게해서 얻어신 left와 right를 통해 reverse를 해주고, 각 값을 저장을 위해 resultLeft[0],resultRight[0]에 저장을 한다

그리고 개수 count를 증가시킨다

 

이 반복이 끝나면 count개수도 0 또는 1 또는 2 또는 3이 생기게 된다

 

그러면 0,1,2 경우는 각 케이스별로 잘 출력하면 되지만 3인 경우는 뒤에서부터 다시 계산이 필요하다

그렇기때문에 원래 입력받은 배열이 필요하므로 처음에 array[i]를 입력받을때부터 temp[i]까지 같이 저장을 해두었다

 

위 코드와 방향을 바꾼채로 i=n부터 i=1까지 감소시키며 left, right를 찾아 reverse 시키고, resultLeft[count], resultRight[count] 로 저장한 다음 count 증가, 다시 반복하는 식이다

 

그러면 정상적으로 count가 0 또는 1 또는 2로 나뉘게 된다

 

2인 경우는 resultLeft[0] resultRight[0] , resultLeft[1] resultRight[1] 출력하고

1인 경우는 resultLeft[0] resultRight[0] 출력과 임의의 i i인 1 1을 출력한다

0의 경우는 1 1을 두번 출력한다