[ SWEA 7991 ] 줄 세우기 (C++)

SWExpertAcademy의 줄 세우기(7991 / D5) 문제이다.

[ 문제풀이 ]

주어진 조건에 맞게 학생들을 줄을 세웠을 때, 사전 순으로 가장 앞선 수열을 구해야 하는 문제이다.

문제에 어떻게 접근하면 좋을지부터 정답을 도출하는 과정까지 진행해보자.

1. 직관적 접근

우리는 키 순으로 수열을 만들었을 때, "가장 앞 선" 수열을 찾고자 하는 것이다.

그러면 ! 가장 앞 선 수열을 만들기 위해서는 입력으로 주어지는 수열을 어떻게 만든 채로 문제에 접근하는 것이 가장 좋을지를 생각해보자.

아마도, 주어진 수열을 "오름차순"으로 정렬 시킨 후에 정답에 맞는 수열로 조금씩 변경하는 것이 가장 유리할 것이다.

하나의 예를 들어보자.

[ 3 2 4 1 ] 이라는 수열이 주어졌다고 가정해보자. 이 수열은 딱 보더라도 이 자체만으로도 정답이 될 수 있다.

하지만 ! 우리가 원하고자 하는 것은 "가장 앞 선" 수열이다. 따라서 이를 오름차순으로 정렬시키게 되면 [ 1 2 3 4 ]가 될 것이고, 이 수열은 문제의 조건에 위배되는 수열이다. 그러면 [ 1 2 3 4 ] 에서 값들을 조금씩 변경함으로써 답을 도출하게 된다면

아마 [ 1 3 2 4 ] 가 정답이 될 것이다. (이 수열은 주어진 TestCase 2번 예시입니다.)

따라서 ! 우리는 직관적으로 봤을 때, 가장 앞 선 수열을 찾기 위해서는 오름차순으로 주어진 배열을 정렬시킨 후 조건에 맞게 줄을 세우는 과정으로 만드는 것이 더 유리하다는 것을 추측할 수 있다.

2. 문제풀이

지금부터는 주어진 TestCase 1번과 2번을 상황에 맞게 적절히 사용해가면서 문제를 풀어보자.

TestCase1 : [ 1 1 1 2 2 ]

TestCase2 : [ 1 2 3 4 ]

1번 Case를 가지고 진행해보자.

(지금부터 배열의 가장 첫번쨰 값을 1번 Index, 배열의 가장 마지막 값을 N번 Index라고 표현하겠습니다.)

1번 Case에서 조건에 위배되는 부분을 찾아본다면, 아마 3번 Index값과 4번 Index값이 조건에 위배되어진다.

왜냐하면, Arr[3] = 1 , Arr[4] = 2 로써, A[i + 1] = A[i] + 1 이라는 수식이 성립되기 때문이다.

그러면 여기서 잠깐 2번 Case를 가지고 한번 이야기를 해보자.

2번 Case에서는 1번 Index와 2번 Index값이 조건에 위배되어진다.

그러면 우리에게는 이 1번 Index와 2번 Index를 가지고 조건에 맞게 바꾸기 위해서 가장 단순하게 접근했을 때, 2가지 방법이 있다.

[ 1 2 3 4 ] 에서 1번 Index와 2번 Index의 자리를 바꾸는 것이다. 즉 배열을 [ 2 1 3 4 ] 의 형태로 만드는 것이다.

조건에 위배되지 않는 배열로 바뀌게 된다.

또 하나의 방법은 1번 Index를 그대로 냅두고, 2번 Index와 그 다음 Index의 값을 바꿔주는 것이다.

즉, 배열을 [ 1 3 2 4 ] 의 형태로 바꿔주는 것이다.

[ 2 1 3 4 ] 와 [ 1 3 2 4 ] 중, 어떤 것이 더 앞선 수열일까 ?? 바로 [ 1 3 2 4 ] 이다.

즉 ! 우리는 여기서 조건에 위배되는 상황을 만났을 때, 1차적인 해결 방법을 알 수 있다.

바로 "A[i] + 1 = A[i + 1]일 때, swa(A[i + 1], A[i + 2]) 를 진행하는 것" 이다.

물론 ! 굉장히 위의 수식이 이상하다고 생각될 것이다. 왜냐하면, 위의 수식은 정말로 2번 Case에 딱 맞춰진 경우에만 부합하는 이야기이고, 다른 경우에는 먹히지 않는 수식이기 때문이다. 하나의 예를 들어보면, A[i + 1] = A[i + 2] 인 이런 경우이다.

이런 경우에 대해서는 밑에서 차근차근 이야기 하도록 하고, 우리가 이 2번 Case를 통해서 알 수 있었던 것은,

"A[i] + 1 = A[i + 1]일 때, i + 1번 이후의 값들과 A[i + 1]의 값들의 자리를 바꿔주는 것이 사전순으로 앞 선 수열이 될 가능성이 굉장히 높다" 라는 것이다.

그럼 다시 1번 Case로 돌아와보자.

[ 1 1 1 2 2 ] 에서 우리는 3번과 4번 Index에 문제가 있음을 발견했다.

그리고 우리가 2번 Case를 통해서 알 수 있었던 것은, [ 1 1 2 1 2 ] 로 바꾸는 것 보다는, [ 1 1 1 2 2 ] 에서 4번 Index이후의 값들과 4번 Index와의 값을 바꾸는 것이 사전순으로 더 앞 선 수열이 가능성이 높다는 것을 알았다.

그럼, 어떤 값이랑 바꿔줘야할까 ??

여기서 바로 위에서 이야기했던 "다른 경우에는 먹히지 않는 수식" 의 경우가 발생했다.

[ 1 1 1 2 2 ] 에서 4번 이후의 Index와 바꿀 적절한 값을 찾아봤더니, 값이 없다. 왜 ?? 5번 Index랑 바꾼다고 하더라도, 4번 Index와 5번 Index를 바꿔도 수열은 그대로 [ 1 1 1 2 2 ] 로써, 조건에 위배되기 때문이다.

여기서 이야기한 "적절한 값"이라는 것은, "자리를 바꿔줌으로써 조건에 위배되지 않는 값"을 의미한다.

즉 ! 여기서는 i + 1번 이후의 값들 중, 바꿀 수 있는 적절한 값이 없는 상황이 된 것이다.

이런 경우에는 어쩔 수 없이 상대적 앞쪽에서 바꿀 적절한 값을 찾아주는 과정이 필요하다.

정리해보면, 3번 Index와 4번 Index에서 문제가 발생했고, 이를 해결하기 위해서 1차적으로 4번 Index이후에 있는 값들 중, 4번 Index와 자리를 바꿀만한 적절한 값을 찾아봤지만 없다는 것을 알게 된 상태이다.

따라서, 지금부터는 2차적으로 3번 Index이전에 있는 값들 중, 3번 Index와 자리를 바꿀만한 적절한 값을 찾아주어야 한다.

그런데 ! 또 찾아보면 그런 값이 없다. 왜 ? 1번, 2번, 3번 Index모두 '1'이기 때문에, 그 누구와 자리를 바꾸더라도, 조건에 계속해서 위배되어 지기 때문이다.

이런 경우에는 가장 첫 번쨰 숫자와 바꿔주는 것이 유일한 해결책이다.

즉 ! [ 1 1 1 2 2 ] 라는 배열을 [ 2 1 1 1 2 ] 로 바꿔주는 것이다. 그렇게 되면, 지금 당장 문제였던 3번 Index와 4번 Index간의 문제가 사라지게 되었다.

이어서 진행해보자. 그 다음 4번 Index와 5번 Index에서 또 문제가 발생하였다.

위에서 진행했던 대로 적절한 값을 찾아보자.

1. 1차적으로 5번 Index이후에 있는 값들 중 적절한 값을 찾아본다.

- 5번 Index가 마지막 값이기 떄문에 그 이후에 있는 값들 중 적절한 값을 찾을 수 있을리 없다.

2. 2차적으로 4번 Index이전에 있는 값들 중 적절한 값을 찾아본다.

- 찾아보니, 1번 Index에 '2'가 있으므로, 5번 Index에 있는 '2'가 2번 Index로 가게 된다면 조건에 위배되지 않을 것이다.

즉, 바꿔주게 되면, [ 2 2 1 1 1 ] 이라는 배열이 완성되어진다.

이게 이 Case의 정답이 된다.

#3. 적절한 값 찾기

#2 과정에서 '적절한 값' 이라는 이야기를 너무 많이했는데, 이 값에 대해서 조금만 더 구체적으로 알아보자.

우리가 조건에 위배되지 않는 수열을 만들기 위해서는 다음과 같은 과정을 진행해 주었다.

< A번 Index와 A + 1번 Index가 조건에 위배되는 상황 >

1. 1차적으로 A + 1번 이후에 있는 값들 중, "적절한 값"을 찾아준다.

2. 1번과정에서 "적절한 값"을 찾지 못했다면, A번 이전에 있는 값들 중, "적절한 값"을 찾아준다.

3. 2번과정에서 "적절한 값"을 찾지 못했다면, 1번 Index와 A + 1번 Index를 바꿔주는 것이 유일한 방법이다.

4. 2번과정에서 "적절한 값"을 찾았다면, 바꿔주면 된다.

이런식으로 정리를 했었는데, 이 "적절한 값"을 찾는 과정에 대해서 조금만 더 알아보자.

#3 - 1) 1번과정 : A + 1번 이후에 있는 값들 중, "적절한 값" 찾기

가장 1차적으로 A + 1번 이후에 있는 값들 중 적절한 값을 찾아준다고 했는데, 이 경우에 중요한 것은, A + 1번 값과 다른 값을 찾는 것이다.

즉, Arr[A + 1] != Arr[A + 1번 이후의 값] 을 만족하는 적절한 값을 찾는 것이다.

즉 ! 기준이 되는 값이 A + 1번째 값이 되는 것이다.

배열이 [ 1 2 3 4 ]가 있을 때, 1번과 2번 Index에서 문제가 발생했고, 이를 해결하기 위해서 A + 1번 이후에 있는 값들 중 찾은 적절한 값은 '3'이였다. 왜 ? 2번 Index가 가진 값과 다른 값을 가진 첫 번째 Index였기 때문이다.

#3 - 2) 2번과정 : A번 이전에 있는 값들 중, "적절한 값" 찾기

이 경우에는 기준이 되는 값이 A번 값이 된다.

[ 1 1 1 2 2 ] 에서 1번과정을 통해서 적절한 값을 찾지 못했을 때, A번 이전에 나온 값들 중 적절한 값을 찾게 된다.

즉, Arr[A] != Arr[A 이전의 값] 을 만족하는 적절한 값을 찾는 것이다.

즉 ! 기준이 되는 값은 A번째 값이 되는 것이다.

#3 - 3) 3번과정 : 2번과정에서 적절한 값을 찾지 못했을 때

[ 1 1 1 2 2 ] 에서는 1번과정을 통해서도, 2번과정을 통해서도 적절한 값을 찾지 못하는 상황이 발생했다.

이 경우에는 위에서도 이야기했듯이, A + 1번째 값과, 1번 값을 바꿔주는 것이 유일한 방법이다.

즉, 주어진 배열을 [ 2 1 1 1 2 ] 로 만들어 주는 것이 유일한 방법이 된다는 것이다.

#3- 4) 4번과정 : 2번과정에서 적절한 값을 찾았을 때

[ 2 1 1 1 2 ] 이 배열에서 4번 Index와 5번 Index를 한번 보자.

1번과정을 통해서는 적절한 값을 찾지 못했기 떄문에 2번과정을 통해서 4번 이전에 있는 값들 중 적절한 값을 찾아야 한다.

위에서도 이야기했듯이, 2번 과정에서는 기준이 되는 값이 'A번째' 값이 된다.

즉, '1'과 다른 값을 가지는 값을 찾아야 한다. 찾아보니, 1번 Index에 '2'라는 값이, '1'과 다른 값을 가지고 있다.

이 때, 비교는 A번 Index와 A번 이전의 Index를 비교했지만, 실제로 값의 변경은, A + 1번과 일어나게 된다.

- 4번과 5번 Index에서 문제발생

- 2번과정을 통해 적절한 값을 찾아보니, '1번Index'에 존재.

- 값의 변경은, 1 + 1번 Index와 , A + 1번 Index간에 일어나게 된다.

즉, 주어진 배열이 [ 2 2 1 1 1 ] 이 되는 것이다.

[ 소스코드 ]

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
 
#define endl "\n"
#define MAX 5010
using namespace std;
 
int N, Idx;
int Arr[MAX];
 
void Initialize()
{
    
}
 
void Input()
{
    cin >> N;
    for (int i = 1; i <= N; i++) cin >> Arr[i];
}
 
void Solution()
{
    sort(Arr + 1, Arr + N + 1);
    for (int i = 1; i < N; i++)
    {
        int Prev = Arr[i];
        int Next = Arr[i + 1];
        if (Prev + 1 == Next)
        {
            int P_Idx = i;
            int N_Idx = i + 1;
            bool Flag = false;
            while (N_Idx <= N)
            {
                if (Arr[N_Idx] != Next)
                {
                    Flag = true;
                    break;
                }
                N_Idx++;
            }
 
            if (Flag == true)
            {
                int Temp = Arr[i + 1];
                Arr[i + 1] = Arr[N_Idx];
                Arr[N_Idx] = Temp;
            }
            else
            {
                while (P_Idx >= 1)
                {
                    if (Arr[P_Idx] != Prev) break;
                    P_Idx--;
                }
                
                if (P_Idx == 0)
                {
                    int Temp = Arr[i + 1];
                    Arr[i + 1] = Arr[1];
                    Arr[1] = Temp;
                }
                else
                {
                    int Temp = Arr[i + 1];
                    Arr[i + 1] = Arr[P_Idx + 1];
                    Arr[P_Idx + 1] = Temp;
                }
            }
        }
    }
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
 
        cout << "#" << T << " ";
        for (int i = 1; i <= N; i++) cout << Arr[i] << " ";
        cout << endl;
        
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}