Coding Test/SWEA

[SWEA] 최대 상금(1244) - Python(DFS)

도구혜지루루 2023. 10. 28. 01:16
728x90
반응형

주어진 숫자를 서로 교환하여, 모두 교환했을 때 가장 큰 수를 출력하는 문제이다.

 

 

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

swexpertacademy.com


테스트 케이스

 

[TC1]

입력 : 123 1

출력 : 321

 

[TC2]

입력 : 2737 1

출력 : 7732

 

[TC3]

입력 : 32888 1

출력 : 88832

 


해결 과정

처음 문제를 풀 때는 경우의 수를 고려하여 조건을 설정하면 풀 수 있겠구나 했는데 생각보다 조건이 많고, for문을 여러번 사용해야 해서 시간 초과가 됐다. 그래서 DFS를 이용하여 모든 경우의 수를 다 구하고, 최대값을 계속 갱신하는 방법을 풀었다.

 


코드

T = int(input())
 
def dfs(start, cnt):
    global chance, nums, max_
    if cnt == chance:
        result = ''
        for v in nums:
            result += v
        result = int(result)
        max_ = max(max_, result)
        return
 
    for i in range(start, len(nums)):
        for j in range(i + 1, len(nums)):
            nums[i], nums[j] = nums[j], nums[i]
 
            dfs(i, cnt + 1)
 
            nums[i], nums[j] = nums[j], nums[i]
 
 
for test_case in range(1, T + 1):
    num, chance = map(int, input().split())
    num = str(num)
    nums = list(num)
 
    max_ = 0
     
    if len(nums) < chance:
        chance = len(nums)
 
    dfs(0, 0)
 
    print(f'#{test_case} {max_}')

 

주서 처리

T = int(input()) # TC 입력 받음
 
def dfs(start, cnt): # 시작점과 교환횟수를 인자로 바등ㅁ
    global chance, nums, max_ # 전역변수 선언
    if cnt == chance: # 다 교환했으면
        result = ''
        for v in nums:
            result += v # result에 모두 저장
        result = int(result) # 숫자로 변환
        max_ = max(max_, result) # 이전 max_ 값과 result를 비교해서 더 큰 값을 max_에 넣음
        return # 함수 종료
 
    for i in range(start, len(nums)): # 시작점부터 끝까지
        for j in range(i + 1, len(nums)): # 시작점 다음부터 끝까지
            nums[i], nums[j] = nums[j], nums[i] # 서로 교환
 
            dfs(i, cnt + 1) # 교환횟수를 1증가시켜 dfs
 
            nums[i], nums[j] = nums[j], nums[i] # 원상복구
 
 
for test_case in range(1, T + 1): # TC 동안
    num, chance = map(int, input().split()) # 숫자와 교환 횟수 받음
    num = str(num) # 숫자를 string으로
    nums = list(num) # 다시 리스트로 변환
 
    max_ = 0 # 출력할 결괏값
     
    if len(nums) < chance: # 시간 초과 최적화
        chance = len(nums) # 교환 횟수가 길이보다 길면 더 안 해봐도 된다
 
    dfs(0, 0) # dfs 시작
 
    print(f'#{test_case} {max_}') # 출력
728x90
반응형