문제 개요
음이 아닌 정수가 하나 주어졌을 때, 두 자릿수를 최대 한 번만 교환하여 만들 수 있는 가장 큰 수를 구하는 문제입니다. 예를 들어 입력값이 2736이라면 출력은 7236이 됩니다. 이는 첫 자리의 2와 그 다음 자리의 7을 서로 바꾸었기 때문입니다.
해결 접근 방법
이 문제는 다음 단계에 따라 해결할 수 있습니다:
- num: 주어진 숫자의 각 자릿수를 분리하여 리스트로 만듭니다.
- num1: num을 내림차순으로 정렬합니다.
- index: 0으로 초기화합니다.
- index가 num의 길이보다 작은 동안 아래 과정을 반복합니다:
- num1[index]와 num[index]가 서로 다르다면:
- a := num의 index+1번째 요소부터 끝까지의 부분 리스트로 지정
- a를 역순으로 뒤집습니다.
- a := len(a) − a.index(num1[index]) + index + 1 − 1 로 교환할 위치를 계산합니다.
- num[index]와 num[a]의 값을 서로 교환합니다.
- 반복문을 종료(break)합니다.
- 그렇지 않으면 index를 1 증가시킵니다.
- num1[index]와 num[index]가 서로 다르다면:
- 마지막으로 num의 각 자릿수를 이어 붙여 정수로 변환한 뒤 결과를 반환합니다.
핵심 아이디어
원본 숫자와 내림차순으로 정렬한 결과를 왼쪽부터 비교하면, 처음으로 값이 달라지는 위치가 바로 '더 큰 숫자와 교환하면 이득'인 자리입니다. 그 위치보다 오른쪽에 있는 숫자들 중 가장 큰 값(중복이 있다면 가장 오른쪽에 있는 값)을 찾아 앞자리의 작은 숫자와 맞바꾸면 한 번의 스왑으로 최댓값을 얻을 수 있습니다. 리스트를 뒤집고 인덱스를 계산하는 과정은 중복된 큰 숫자 중 가장 마지막(오른쪽) 위치를 정확히 찾기 위함입니다.
예제 코드(Python)
더 나은 이해를 위해 다음 구현을 살펴보겠습니다.
class Solution:
def maximumSwap(self, num):
num = list(map(int,list(str(num))))
num1 = sorted(num,reverse=True)
index=0
while index<len(num):
if num1[index]!=num[index]:
a = num[index+1:]
a.reverse()
a=len(a) - a.index(num1[index])+index+1 -1
num[index],num[a] = num[a],num[index]
break
index+=1
return int("".join(str(x) for x in num))
ob1 = Solution()
print(ob1.maximumSwap(5397))
입력
5397
출력
9357
결과 분석
입력값 5397에서 첫 번째 자리의 5와 세 번째 자리의 9를 교환하면 9357이 됩니다. 내림차순 정렬 결과인 9753과 비교했을 때 가장 먼저 차이가 나는 첫 자리에서 가장 큰 숫자인 9를 앞으로 가져오는 것이 한 번의 스왑으로 만들 수 있는 최선의 선택임을 확인할 수 있습니다.