파이썬 알고리즘: 한 자릿수를 3으로 바꿔 만들 수 있는 최대 숫자 구하기

정수 n이 주어지며, 이 수에는 1, 2, 3 세 가지 자릿수만 포함되어 있다고 가정해 보겠습니다. 우리는 단 하나의 자릿수를 3으로 바꿀 수 있으며, 그 결과 만들 수 있는 최대 숫자를 구해야 합니다.

예를 들어 입력값이 11332라면, 맨 앞자리의 1을 3으로 바꾸어 출력은 31332가 됩니다.

해결 방법

이 문제는 다음 단계를 따라 해결할 수 있습니다.

n의 각 자릿수를 요소로 하는 리스트 li를 생성합니다.
x를 0부터 리스트 길이 - 1까지 반복합니다.
- 만약 li[x]가 '3'이 아니라면,
  - li[x]를 '3'으로 변경합니다.
  - 리스트의 자릿수들을 이어 붙여 정수로 변환한 뒤 반환합니다.
모든 자릿수가 이미 3이라면 원래 값 n을 그대로 반환합니다.

핵심 아이디어는 매우 간단합니다. 숫자를 최대한 크게 만들려면 자릿수가 높은 쪽, 즉 왼쪽에 있는 숫자를 큰 값으로 바꾸는 것이 유리합니다. 따라서 왼쪽부터 차례대로 탐색하면서 처음 발견되는 3이 아닌 자릿수를 3으로 바꾸면 항상 최댓값을 얻을 수 있습니다.

구현 예시

아래 코드를 통해 더 잘 이해해 보겠습니다.

class Solution:
   def solve(self, n):
      li = list(str(n))
      for x in range(len(li)):
         if li[x] != '3':
            li[x] = '3'
            return int(''.join(li))
      return n
ob = Solution()
print(ob.solve(11332))