[ day 7 ] 계기판 조작하기

계기판 조작하기

• 시간 제한: 1초

엘리스는 악질 중고차 딜러인 체셔를 싫어해 체셔를 골탕 먹이려고 합니다.

엘리스는 순식간에 자동차 주행거리 계기판을 조작할 수 있는 기술을 가지고 있습니다. 엘리스는 차를 구경하겠다고 체셔에게 부탁한 뒤 구경하는 시간 동안 계기판의 주행거리를 더 크게 조작해 체셔가 당황하게 만들 예정입니다.

원래 자동차의 주행거리가 N킬로미터면 여러분은 체셔에게 들키지 않도록 주행거리를 N보다 크면서, 가장 작은 수로 늘려놓으려고 합니다. 이때, 조작한 값은 서로 다른 K개의 숫자로 이루어져야 합니다. 예를 들어, 100000이란 수는 1과 0으로 이루어져 있으므로, 2개의 숫자로 이루어진 수입니다.

N과 K를 줬을 때 조작할 수 있는 주행거리의 최솟값을 출력하는 프로그램을 작성하세요.

 

지시사항

입력

• 첫 번째 줄에 자연수 N과 K를 입력합니다.
  
  1≤N≤107
  
  
  1≤K≤10
• 주행거리를 조작한 값이 전과 비교해 더 큰 경우만 입력합니다.

출력

• 첫 번째 줄에 조작할 수 있는 주행거리의 최솟값을 출력합니다.

입력 예시

100000 3

출력 예시

100002

 

 

 

 

 

정답 코드

C++

#include <algorithm>
#include <iostream>
#include <string>

using namespace std;

bool digit[10];
int main() {
  int K, cnt = 0;
  string N;
  cin >> N >> K;
  if (K == 10)
    cout << "1023456789";
  else if (K == 9)
    cout << "102345678";
  else {
    while (cnt != K) {
      fill_n(digit, 10, false);
      cnt = 0;
      N = to_string(stoi(N) + 1);
      for (int i = 0; i < N.length(); i++)
        digit[N[i] - '0'] = true;
      for (int i = 0; i < 10; i++)
        if (digit[i])
          cnt++;
    }
    cout << N;
  }
}

 

 

Python

from functools import reduce

n, k = map(int, input().split())
used = [False for _ in range(10)]
nofd, arr = len(str(n)), [int(x) for x in str(n)]


def magic_num(m, l):
    if l < 0 or l > m:
        return -1
    if (m, l) == (0, 0):
        return 0
    digit_t = [x for x in range(10) if used[x]]
    digit_f = [x for x in range(10) if not used[x]]
    digit = sorted(digit_t[:1] + digit_f[:l])
    return reduce(lambda x, y: 10 * x + y, digit[:1] * (m - l) + digit_f[:l], 0)


if k > nofd:
    print("10" + "".join(map(str, range(2, k))))
elif n > int("9" * (nofd - k) + "".join(map(str, range(9, 9 - k, -1)))):
    print("100" + "0" * (nofd - k) + "".join(map(str, range(2, k))))
else:
    count, idx = 0, nofd - 1
    for i in range(nofd):
        if not used[arr[i]]:
            count, used[arr[i]] = count + 1, True
            if count > k:
                idx = i
                break
    if count == k:
        print(n)
    else:
        result = -1
        for i in range(idx, -1, -1):
            for j in range(10):
                used[j] = False
            for j in range(i):
                used[arr[j]] = True
            for j in range(arr[i] + 1, 10):
                temp, used[j] = used[j], True
                result = magic_num(nofd - 1 - i, k - sum(used))
                if result >= 0:
                    print(
                        n
                        - (n % (10 ** (nofd - i)))
                        + j * (10 ** (nofd - i - 1))
                        + result
                    )
                    break
                used[j] = temp
            if result >= 0:
                break

 

Java

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String N = scanner.next();
        int K = scanner.nextInt();
        scanner.close();
        
        boolean[] digit = new boolean[10];
        int cnt = 0;
        
        if (K == 10) {
            System.out.println("1023456789");
        } else if (K == 9) {
            System.out.println("102345678");
        } else {
            while (cnt != K) {
                Arrays.fill(digit, false);
                cnt = 0;
                N = Integer.toString(Integer.parseInt(N) + 1);
                for (int i = 0; i < N.length(); i++) {
                    digit[N.charAt(i) - '0'] = true;
                }
                for (int i = 0; i < 10; i++) {
                    if (digit[i]) {
                        cnt++;
                    }
                }
            }
            System.out.println(N);
        }
    }
}