[1039] 교환

문제 링크 : https://www.acmicpc.net/problem/1039

1039 - 교환

본문

0으로 시작하지 않는 정수 $N$이 주어진다. 이때, $M$을 정수 $N$의 자릿수라고 했을 때, 다음과 같은 연산을 $K$번 수행한다.

$1 \leq i < j \leq M$인 $i$와 $j$를 고른다. 그 다음, $i$번 위치의 숫자와 $j$번 위치의 숫자를 바꾼다. 이때, 바꾼 수가 0으로 시작하면 안 된다.

위의 연산을 $K$번 했을 때, 나올 수 있는 수의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 $N$과 $K$가 주어진다. $N$은 $1\,000\,000$보다 작거나 같은 자연수이고, $K$는 $10$보다 작거나 같은 자연수이다.

출력

첫째 줄에 문제에 주어진 연산을 $K$번 했을 때, 만들 수 있는 가장 큰 수를 출력한다. 만약 연산을 $K$번 할 수 없으면 -1을 출력한다.

제한

시간 제한	메모리 제한
2sec	128MB

---

풀이

문제에서 원하는 것을 잘 보자. 자리수를 $K$번만큼 바꾸는 연산을 수행했을 때 만들 수 있는 수의 최댓값을 찾고 싶다. 말에서 함정이 하나 있는데, $K$번의 연산을 꼭 다 써야한다. 즉 1번만 바꿔서 최댓값을 만들 수 있다고 하더라도, 그것이 정답이 될 수 없다.

그렇다면, 현재 만들 수 있는 수들에서 1번의 연산을 통해 만들어낼 수 있는 수들을 후보로 지정하고, 그 결과를 기록할 수 있다면, round마다 만들 수 있는 후보들을 기록할 수 있을 것이고, $K$번의 round가 모두 끝났을 때 만들 수 있는 후보들 중 가장 큰 값이 정답이 될 것이다. 그러면 모든 수에 대해서 1번 수의 위치를 바꾸는 모든 과정을 하나의 round로 생각하고 코드를 짤 수 있다.

round는 아래와 같이 진행될 수 있다.

• 후보 수들 중 하나를 고른다
  • 고른 후보 수에서, 수의 위치를 바꿀 2곳을 선택한다
  • 그 위치들의 수를 바꿀 수 있는지 확인한다
    • 같은 자리의 숫자는 바꿀 수 없다
    • 바꾸었을 때 수는 0으로 시작하면 안된다
  • 수의 위치를 바꾸는 것이 가능하다면 바꾸고, 그 때의 수를 다음 후보 수로 저장한다

최종적으로 $K$번의 round가 모두 끝났다면 후보 수들 중 최댓값을 출력하면 된다.

후보 수를 저장해두는 방법은 배열을 사용하여 저장할 수 있다. bool 배열을 만들어서 그 수를 만들 수 있다면 그 위치를 true로 바꾸어주는 것이다. round를 시작할 때, 모든 수들 중 true인 수들만 빼서 큐에 저장해두고 배열을 false로 초기화해주면, 배열을 새로 활용할 수 있으면서도 후보 수를 round마다 분리하여 저장해둘 수도 있게 된다. $K$번의 round가 모두 끝났다면 true인 수들 중 최댓값을 찾으면 되는 것.

앞서 얘기했듯이 문제에 함정이라고 생각될 만한 요소가 있고, 이외에도 쉽게 코딩하면 여러 반례에 부딫힐 가능성이 높다. 내가 풀면서 맞닥뜨린 반례는 아래가 있다.

100 3
output : -1
answer : 100

같은 output이 나왔다면, 왜 저런 output이 나왔는지 생각해보도록 하자.

• 참고 알고리즘 :

코드

사용 언어 : C

최종 수정일 : 2023 / 11 / 3

#include <stdio.h>

typedef char bool;
const bool true = 1;
const bool false = 0;

#define MAX_IDX (int)(1e6)

bool visit[MAX_IDX + 1];
int n, k;
int digit;

int queue[MAX_IDX + 1];
int front, rear;
bool isCandidateExists;

void clear() {
    for (int i = 0; i <= MAX_IDX; ++i) {
        visit[i] = false;
    }
    isCandidateExists = false;
    return;
}

int getDigit(int x, int a) {
    for (int i = 0; i < a; ++i) {
        x /= 10;
    }
    return x % 10;
}

int swap(int x, int a, int b) {
    int c = 1, d = 1;
    for (int i = 0; i < a; ++i) {
        c *= 10;
    }
    for (int i = 0; i < b; ++i) {
        d *= 10;
    }

    int e = (x / c) % 10, f = (x / d) % 10;
    int ret = x - (e * c) - (f * d) + (f * c) + (e * d);

    return ret;
}

int main() {
    scanf("%d %d", &n, &k);
    visit[n] = true;

    int temp = n;
    while (temp > 0) {
        temp /= 10;
        ++digit;
    }

    for (int i = 0; i < k; ++i) {
        for (int j = 0; j <= MAX_IDX; ++j) {
            if (visit[j] == true) {
                queue[rear++] = j;
            }
        }
        clear();

        while (front < rear) {
            int x = queue[front++];
            for (int a = 0; a < digit; ++a) {
                for (int b = a + 1; b < digit; ++b) {
                    if (b == digit - 1 && getDigit(x, a) == 0) {
                        continue;
                    }
                    visit[swap(x, a, b)] = true;
                    isCandidateExists = true;
                }
            }
        }

        front = rear = 0;
        if (isCandidateExists == false) {
            printf("-1");
            return 0;
        }
    }

    for (int i = MAX_IDX; i >= 0; --i) {
        if (visit[i] == true) {
            printf("%d", i);
            break;
        }
    }

    return 0;
}