[코드트리] Novice Mid - 수열의 순서 바꾸기

코드트리 - 수열의 순서 바꾸기

https://www.codetree.ai/missions/5/problems/reorder-sequence?&utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

접근을 어떻게 하는지에 따라 난이도가 완전히 달라지는 문제였다.

해결 방법에 대해 직관적으로 이해를 했다면 순식간에 했겠지만, 나 같은 경우에는 너무 빙빙 돌아 생각해서 한참이 걸렸었다.

 

잘못된 접근 - 틀린 코드

#include <iostream>
using namespace std;

int arr[101];

void moving(int movPos)
{
    int movNum = arr[0];
    for(int i=1; i<=movPos; i++)
    {
        arr[i-1] = arr[i];
    }

    arr[movPos] = movNum;
}

int main() 
{
    int n;

    cin >> n;

    for(int i=0; i<n; i++)
    {
        cin >> arr[i];
    }
//1 4 2 3
//4 1 2 3
//
// 자신보다 작은 수 찾아나가기
// 자신보다 큰 수 인데 그 다음수가 그 수보다 작은 경우 -> 옮기기
// 자신보다 큰 수 이지만 다음수가 그 수보다 큰 경우 -> 다음 탐색
// 자신보다 작은 수 인데 그 다음 수도 자신보다 작은 경우 -> 다음 탐색
// 자신보다 작은 수 인데 그 다음수는 자신보다 큰 경우 -> 옮기기
// 탐색이 끝날때까지 이벤트가 없었다-> 마지막 정렬이므로 +1 하고 종료

    int answer = 0;
    while(true)
    {
        bool isMoved = false;
        for(int i=1; i<n-1; i++)
        {
            if(arr[i] > arr[0])
            {
                if(arr[i+1] < arr[i])
                {
                    moving(i);
                    answer += 1;
                    isMoved = true;
                    break;
                }
            }
            else if(arr[i] < arr[0])
            {
                if(arr[i+1] > arr[0])
                {
                    moving(i);
                    answer += 1;
                    isMoved = true;
                    break;
                }
            }
        }

        if(!isMoved)
        {
            answer += 1;
            break;
        }
    }

    cout << answer;
    // 여기에 코드를 작성해주세요.
    return 0;
}

 

너무 복잡하게 생각하고 접근해서 틀렸다.

그래서 계속 고민하고 틀리다 해설을보고 이해한 후 나온 코드는 아래와 같다.

 

정답 코드

#include <iostream>
using namespace std;

int arr[101];
int n;


int main() {

    int arr[101];
    int n;
    cin >> n;

    for(int i=1; i<=n; i++)
    {
        cin >> arr[i];
    }
    
    int cnt = n;
    for(; cnt>=2; cnt--)
    {
        if(arr[cnt] < arr[cnt-1]) break;
    }
    //1 3 2 4

    cout << cnt-1;

    return 0;
}

풀이는 참으로 간단했다. 맨 뒤에서부터 정렬되어있는 수를 카운팅 하면 풀 수 있었던 문제.

직관력이 가장 중요하지 않나... 라는 생각이 드는 요즘이다.