[Day 1] 목표량

 

문제

• 시간 제한: 1초

엘리스 토끼는 목표량을 정해 수학 문제를 열심히 풉니다. 목표량은 정수입니다.
내일 풀 수학 문제의 개수는 오늘 푼 문제 개수의 수와 숫자의 구성이 같으면서, 오늘 푼 문제 개수의 수보다 큰 수 중 가장 작은 수입니다.
예를 들어, 오늘 67문제를 풀었으면 다음 날 76문제를 풉니다.
오늘 푼 문제의 개수를 줬을 때 다음날 풀 문제의 개수를 출력하는 프로그램을 작성하세요.

 

입력

첫 번째 줄에 오늘 푼 문제의 개수인 자연수 N을 입력합니다(1≤N≤999999).
정답이 반드시 있는 경우만 입력값으로 주어집니다.

출력

다음날 풀 문제의 개수를 출력합니다.

 

입력 예시

364

출력 예시

436

 

 

 

 

나의 코드 : DFS 재귀를 사용하였다. 

DFS를 재귀적으로 통해 목표량을 탐색
# 전체 자리수를 탐색하기 전까지(L<D)
- # case1. 현재 숫자가 원래 숫자의 L번째 숫자와 같을 경우: L+1번째 자리와 다음 숫자를 탐색한다.
- # case2. 현재 숫자가 원래 숫자의 L번째 숫자보다 클 경우: 탐색을 종료하고, 사용하지 않은 숫자를 정렬하여 제일 작은 수를 만든다.

input_str = input() #입력 받기 

# 변수 정의 
result = [] # 목표량 만들 int list
num_lst = sorted(list(map(int, input_str))) # 각 자리 숫자 오름차순 정렬해놓은 int list
visited = [False ] *len(num_lst) # 각자리 숫자를 이미 썼는지 알려줌
candidates = [] # 목표량 후보들 
D = len(input_str)

def DFS(L)  :# L: 탐색할 숫자 자리수 인덱스 
    global result
    
    if L >= D: # 만약에 숫자가 모두 만들어진 경우 종료
        result_str = ''.join(map(str, result))
        if result_str!= input_str: # 만든 str이 본인이 아닐 경우에만 저장 
            candidates.append(result_str)
        return
    # 숫자 리스트의 모든 수에 대해서
    for i, num in enumerate(num_lst):
        if not visited[i]: # 사용되지 않은 숫자에 대해서 
            # case1. 원래 숫자의 L번째 숫자와 계속 같을 경우
            if num == int(input_str[L]): 
                result.append(num_lst[i]) # result에 붙임
                visited[i] = True
                DFS(L+1) # 다음 단계 탐색함
                # 원상 복구
                result = result[:-1] 
                visited[i] = False
            elif num > int(input_str[L]): #원래 숫자의 L번째 숫자보다 클 경우,  나머지 숫자를 정렬하여 젤 작은 수를 만든다.
                result.append(num_lst[i]) # result에 붙임
                visited[i] = True
                # 방문하지 않은 숫자들을 오름차순 정렬하여 나머지 str을 만든다.
                unvisited_nums = []
                for j, num in enumerate(num_lst):
                    if not visited[j]:
                        unvisited_nums.append(num)
                #unvisited_nums = [ num if not visited[num] for num in num_lst ]
                candidates.append(''.join(map(str, result)) + ''.join(map(str, unvisited_nums))) # 완성된 str 생성
                # 전역 변수 원상 복구
                result = result[:-1] # result에 붙임
                visited[i] = False
                return

# 함수 수행 
DFS(0)
#결과 인쇄
candidates.sort()
print(candidates[0])

 

 

 

모범코드 : 단순구현

s = list(input())
for i in range(len(s) - 2, -1, -1):
    if s[i] < s[i + 1]:
        break
else:
    print(0)
    exit()
for j in range(len(s) - 1, i, -1):
    if s[j] > s[i]:
        break
s[i], s[j] = s[j], s[i]
s[i + 1 :] = s[:i:-1]
print("".join(s))

 

 

 

느낀 점

너무 복잡하게 구현한 것 같다.