Baek_1038

오늘도 골드문제를 도전했다. 그리고 성공했다ㅎㅎ 사실 저번에 스터디에서 같이 1시간 고민하고 포기했었다.

감소하는수를 찾는 문제라 나는 처음에 에라토스테네스의 체 방식처럼 소수를 리스트 안에 하나씩 True인지 False인지 넣어서 소수를 빨리 찾는 아이디어를 생각했다.
9876이 감소하는 수인지 보려면
9와 8을 비교해서 9가 큰지, 876 리스트의 값이 True인지 보도록 만들었다.
근데 Fail..... 시간초과났다.

1시간을 넘겨서 다음 기회로 넘겼는데 대충 생각난 부분은 전체 수에서 for문 돌려서 찾지 말고 조합해 나가야겠다는 것이다.

오늘 그부분을 고민했는데 생각해보니 조합 문제였다.
0~9까지 있는 리스트에서 숫자를 뽑아 조합을 만들면 감소하는수를 만들 수 있었다.

import sys
sys.stdin.readline
from itertools import combinations as cb
cnt = int(input())

nums = ['9','8','7','6','5','4','3','2','1','0']
pre,cur,length = 0,0,1
flag = True
while cur <= cnt:
    if length > 10:
        flag = False
        break
    comb = cb(nums,length)
    num_list = list()
    pre = cur
    for i in comb:
        cur+=1
        num_list.append(int("".join(i)))
    length+=1
    num_list.sort()
if cnt == 0:
    print(0)
else:
    if flag:
        print(num_list[cnt-pre])
    else:
        print(-1)

cur에는 현재 n값을, pre에는 combination을 돌고 나서 저장시킨다. 목적 cnt값에 도달했을 때 while문을 탈출하고 cnt-pre 인덱스의 값을 출력한다.
재밌는것은 combinations는 0을 취급 안하는 거 같더라... 그래서 0을 예외처리해줬다.
오늘도 보람찬 하루~