BOJ 2697 - 다음수 구하기 (Python)

S2, 문자열, 그리디

풀이

1. 메모리초과 코드

• 가능한 모든 경우의 수를 permutations를 통해 만든 후,
  만들어진 수들 중 주어진 값과 가장 가까운 큰 수를 찾는 로직으로 작성했다.

from sys import stdin
from itertools import permutations
T = int(stdin.readline())

for _ in range(T):
    a = stdin.readline().rstrip()
    num = int(a)
    tmp = []
    for n in a:
        tmp.append(n)

    comb = list(permutations(tmp, len(a)))
    total = []
    for arr in comb:
        w = ''
        for n in arr:
            w += n
        total.append(int(w))
    
    total.sort(reverse=True)

    for i in range(len(total) - 1):
        if total[i] == num:
            print("BIGGEST")
            break
        if total[i + 1] == num:
            print(total[i])

2. 시간초과 코드

• 딕셔너리를 통해 각 값이 얼마나 등장하는 지를 세어 확인 후 비교해나가는 로직을 구성했다.

from sys import stdin
import copy
T = int(stdin.readline())

for _ in range(T):
    a = stdin.readline().rstrip()
    dic = dict()

    for n in a:
        dic[n] = dic.get(n, 0) + 1

    num = int(a)
    k = len(a)
    while 1:
        num += 1
        compare = copy.deepcopy(dic)

        for s in str(num):
            if s in compare.keys():
                if compare[s] > 0:
                    compare[s] -= 1

        if sum(compare.values()) == 0:
            print(num)
            break

        if len(str(num)) > k:
            print("BIGGEST")
            break

3. 문자열 그리디 풀이

• 로직을 생각하는 게 어려웠다.
• 큰 수를 앞으로 옮겨주며 비교하는 그리디 식 풀이법

from sys import stdin
T = int(stdin.readline())

for _ in range(T):
    data = list(map(int, list(stdin.readline().rstrip())))

    k, idx = len(data), 0

    for i in range(k-1, 0, -1):
        if data[i] > data[i - 1]:
            if i == k - 1:
                idx = k - 2
            else:
                idx = i - 1
            break

    a = data[:idx]
    b = data[idx:]

    if not a or not b:
        print("BIGGEST")
    else:
        b.sort()
        for i in range(len(b)):
            if b[i] > data[idx]:
                a.append(b.pop(i))
                a.extend(b)
                break
        print(''.join(map(str, a)))