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
반응형