[백준/C++] 1422번: 숫자의 신

문제 & 링크

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

 

풀이

1. K개의 수를 적어도 한 번씩 사용해야 하기에, 모든 수를 이어 붙여서 가장 큰 수를 구하는 문제와 유사하다.

2. N > K일 경우 숫자를 중복으로 사용하여 추가할 수 있는데, 자릿수와 값을 생각하면 무조건 K개의 수 중 큰 수를 N - K 만큼 붙여야 한다.

3. 숫자를 string으로 바꾸어 사전 순으로 가장 앞서는 수를 구한다. 숫자를 그냥 넣게 될 경우, 아래와 같은 예시가 존재할 수 있다.

  ex) K = { 31, 34 } -> 사전 순으로 정렬: 34, 31 -> 결과: 3431 (기댓값: 3431)

  ex) K = { 3, 34 } -> 사전 순으로 정렬: 34, 3 -> 결과: 343 (기댓값: 343)

  ex) K = { 3, 31 } -> 사전 순으로 정렬: 31, 3 -> 결과: 313 (기댓값: 331)

4.  맨 앞부터 시작하여 대소 관계를 비교(우선순위큐가 자동으로 실행)하고, 만약 비교할 숫자가 없을 경우, 제일 앞 숫자와 비교한다.

  ex) K = {3, 34}

3과 34에서 맨 앞의 숫자 비교 3 & 3, 다음 자리 비교 X & 4 (X: 제일 앞 숫자인 3으로 생각) -> 결과: 343

  ex) K = {3, 31}

3과 31에서 맨 앞의 숫자 비교 3 & 3, 다음 자리 비교 X & 1 (X: 제일 앞 숫자인 3으로 생각) -> 결과: 331

5. 비교할 숫자가 없어서 제일 앞 숫자와 비교했는데, 같은 값일 경우 그 다음 숫자를 비교한다.

  ex) K = {34, 343}

34와 343에서 맨 앞의 숫자 비교 3 & 3, 다음 자리 비교 4 & 4, 다음 자리 비교 X & 3 (X: 제일 앞 숫자인 3으로 생각), 다음 자리 비교 X2 & Y (X2: 제일 앞에서 두 번째 숫자인 4로 생각, Y: 제일 앞 숫자인 3으로 생각) -> 결과: 34343

  ex) K = {31, 313}

31과 313에서 맨 앞의 숫자 비교 3 & 3, 다음 자리 비교 1 & 1, 다음 자리 비교 X & 3 (X: 제일 앞 숫자인 3으로 생각), 다음 자리 비교 X2 & Y (X2: 제일 앞에서 두 번째 숫자인 1로 생각, Y: 제일 앞 숫자인 3으로 생각) -> 결과: 31331

6. 3 - 5번의 내용을 구현하기 위해 입력 받은 값을 10번 반복하여 붙이고, 우선순위큐에 저장한다. 10번 반복하는 이유는 가장 큰 입력값인 1,000,000,000을 무조건 넘게 하기 위함이다.

7. 2번의 case일 경우를 위해 미리 가장 큰 수를 저장해놓고, 우선순위큐에서 pop되는 시점에 N - K만큼 붙인다.

  ex) K = 2 ({3, 34}), N = 3, 가장 큰 수: 34

3과 34에서 맨 앞의 숫자 비교 3 & 3, 다음 자리 비교 X & 4 (X: 제일 앞 숫자인 3으로 생각) -> 결과: 34343

  ex) K = 2 ({3, 31}) , N = 4, 가장 큰 수: 31

3과 31에서 맨 앞의 숫자 비교 3 & 3, 다음 자리 비교 X & 1 (X: 제일 앞 숫자인 3으로 생각) -> 결과: 3313131

 

코드

#include <iostream>
#include <queue>
#include <string>

using namespace std;

int main() {
    priority_queue<string> pq;
    int K, N;
    string ans = "";

    cin >> K >> N;

    string S;
    int max_value = 0;
    for (int i = 0; i < K; i++) {
        cin >> S;
        string tmp = S;
        max_value = max(max_value, stoi(S));

        for (int j = 0; j < 9; j++) tmp += S;

        pq.push(tmp);
    }

    bool empty = true;
    while (!pq.empty()) {
        string str = pq.top();
        pq.pop();

        str = str.substr(0, str.length() / 10);

        if (empty && stoi(str) == max_value) {
            for (int i = 0; i < N - K; i++) {
                ans += str;
            }
            empty = false;
        }

        ans += str;
    }

    cout << ans;
}