[백준 문제 C++] 1039 교환

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

1039번: 교환

#include <stdio.h>
#include <string.h>

char n[10];
int result = -1;

void Swap(int a, int b)
{
    char temp = n[a];
    n[a] = n[b];
    n[b] = temp;
}

char GetMaxNum(int start, int length)
{
    char num = n[start];
    for (int i = start + 1; i < length; ++i)
    {
        if (num < n[i])
        {
            num = n[i];
        }
    }
    return num;
}

bool IsRightOrder(int length)
{
    for (int i = 1; i < length; ++i)
    {
        if (n[i - 1] < n[i])
        {
            return false;
        }
    }

    return true;
}

bool ExistSameNum(int length)
{
    for (int i = 1; i < length; ++i)
    {
        if (n[i - 1] == n[i])
        {
            return true;
        }
    }
    return false;
}

int GetMax(int a, int b)
{
    return a > b ? a : b;
}

int ArrayToNum(int length)
{
    int num = 0;
    for (int i = 0; i < length; ++i)
    {
        num = num * 10 + n[i] - '0';
    }
    return num;
}

void ChangeNumbers(int step, int k, int start, int length)
{
    if (step == k)
    {
        result = GetMax(result, ArrayToNum(length));
        return;
    }

    if (IsRightOrder(length))
    {
        if (!ExistSameNum(length) && (k - step) % 2 == 1)
        {
            Swap(length - 1, length - 2);
            result = GetMax(result, ArrayToNum(length));
            Swap(length - 1, length - 2);
        }
        else
        {
            result = GetMax(result, ArrayToNum(length));
        }

        return;
    }

    if (start + 2 == length)
    {
        Swap(start, start + 1);
        ChangeNumbers(step + 1, k, start, length);
        Swap(start, start + 1);
    }
    else
    {
        char maxNum = GetMaxNum(start, length);

        if (n[start] == maxNum)
        {
            ChangeNumbers(step, k, start + 1, length);
        }

        for (int i = start + 1; i < length; ++i)
        {
            if (n[i] == maxNum)
            {
                Swap(start, i);
                ChangeNumbers(step + 1, k, start + 1, length);
                Swap(start, i);
            }
        }
    }
}

int main()
{
    int k;
    int length;

    scanf("%s %d", n, &k);
    length = strlen(n);

    if (length <= 1 || (length == 2 && n[1] == '0'))
    {
        printf("-1\n");
        return 0;
    }

    ChangeNumbers(0, k, 0, length);
    printf("%d\n", result);
}

처음에 굉장히 쉬운줄 알았는데 예상치 못한 테스트 케이스가 많았던 문제였다.

 

처음부터 알아낸 조건과 삽질하며 알아낸 조건들이 있다. 정리를 해보면

1. 1개면 교환이 불가능하다. (-1 출력)

 

2. 2개일 때 뒤에 0이 있다면 교환이 불가능하다. (-1 출력)

    (여기까지 미리 1~9, 10, 20, 30 ... 90 까지의 숫자는 걸러준다.)

 

3. 당연하게도 무조건 가장 큰 수가 맨 앞으로 가면 좋다! 그러나 고려해야 될 조건이 두 가지 있다.

 

  3-1. 가장 큰 수가 "맨 앞에만" 있다.

        ex) 930 => 9를 스킵하고 30에 대해서만 교환을 해주면 된다.

             97  => 2개이기 때문에 스킵이 불가능하다. 무조건 교환해줘야 된다.

 

  3-2. 가장 큰 수가 "여러개" 일 경우이다.

        (처음에 가장 뒤에놈을 앞으로 옮겨줬는데 아래 테스트 케이스 중 그러면 안되는 것이 있다.)

        ex) 9989 1 => 9998

             3699 2 => 9963

             6399 2 => 9963 (이놈)

 

 4. 이미 차례대로 정렬되어 있다면 마지막 2개만 교환해주거나 교환해줄 필요가 없어진다.

        ex) 9876 1 => 9867,    9876 2 => 9876

             9987 x => (맨 앞의 99만 계속 교환해주면 끝) 9987

 

3번 조건의 가장 큰 수가 여러개 있는 경우에 탐색의 분기점이 생긴다.

그래서 Swap 이 후 다시 Swap을 통해 기존의 배열을 유지시키며 탐색을 하게 만들었다.

 

코드를 보면 나처럼 멍청한 사람이 코딩하면 이렇게 코드가 길어지고 시행착오를 겪게 되며 시간을

많이 쓰게 된다는 것을 다시 느끼게 된다.. ㅠㅠ

다른 사람이 잘 작성한 코드도 보면서 더 쉽고 간결하게 짤 수 있는 방법도 보고 이해해야 된다!