1244. [S/W 문제해결 응용] 2일차 - 최대 상금 D3

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&problemLevel=4&contestProbId=AV15Khn6AN0CFAYD&categoryId=AV15Khn6AN0CFAYD&categoryType=CODE&problemTitle=&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=4&pageSize=10&pageIndex=1 

SW Expert Academy

 

import sys
 
sys.stdin = open('input.txt')
 
#테스트케이스 종류
def dfs(cnt, target): # 지금 횟수와 연산횟수를 인수로
    global answer #정답은 계속 초기화시켜주기
    if cnt == target:  # 지금 횟수와 연산횟수가 같아서 마지막 연산이라면
        temp = ''.join(nums)  # 문자 한개씩 되있는걸 합침
        if answer < temp:  # answer에 저장되어있는 값보다 크다면 갱신
            answer = temp
        return #answer만 초기화시켜주면 되므로 return값은 없음
 
    for i in range(len_nums): #완전탐색해야함으로 문자열길이만큼 반복
        for j in range(i + 1, len_nums):  # 현재 자리(i)의 다음자리부터 비교
            nums[i], nums[j] = nums[j], nums[i]  # 이렇게하면 모든 자리는 한번씩 다 바뀜(완전탐색)
            temp = ''.join(nums)  # 바뀌고 바로바로 문자열로 합침
 
            if visited.get((temp, cnt), 1):  # visited에 (바꾼 문자열, 지금 횟수)이 중복이 안되서 없다면 default값인 1출력되서 실행
                visited[(temp, cnt)] = 0  # visited에 (temp,cnt):0 으로 저장
                dfs(cnt + 1, target)  # 다시 실행시킴 -> target만큼 실행시켜야하므로 dfs()사용
                                      # 이러면 중복을 제외하고 target만큼 실행시킨 완전탐색을 하게 됨.
            nums[i], nums[j] = nums[j], nums[i]  # for문 처음으로 돌아가기 때문에 원상복구를 해야함.
 
 
for test in range(1, int(input()) + 1): #테스트 케이스를 받음
    nums, target = input().split()
    target = int(target)
    nums = list(nums) #문자열을 문자 1개씩 리스트로 만듦
    len_nums = len(nums) #문자열의 길이
    visited = {}  # 중복되는 거 방지해야함.
    answer = '000000'  # 최대 6자리이므로 정답 표시할 문자 6개
 
    dfs(0, target) #완전탐색
 
    print('#{} {}'.format(test, answer))