Python으로 숫자의 임의 위치에 5를 삽입해 만들 수 있는 최댓값 구하기

숫자 n이 주어졌을 때, 이 숫자의 임의의 위치에 5를 한 번 삽입하여 얻을 수 있는 최댓값을 찾는 문제입니다.

예를 들어 입력이 n = 834라면, 5를 두 번째 자리 앞에 삽입한 8534가 가장 큰 수이므로 출력은 8534가 됩니다.

해결 접근 방법

이 문제는 그리디(Greedy) 방식으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 숫자의 부호에 따라 5를 삽입할 최적의 위치가 달라진다는 점입니다.

양수인 경우: 왼쪽부터 탐색하면서 처음으로 5보다 작은 숫자 앞에 5를 삽입하면 값이 가장 커집니다. 만약 그런 숫자가 없다면(모든 자릿수가 5 이상이라면) 맨 뒤에 추가합니다.
음수인 경우: 음수에서는 절댓값이 작을수록 실제 값이 커지므로, 왼쪽부터 탐색하면서 처음으로 5보다 큰 숫자 앞에 5를 삽입합니다. 그런 숫자가 없다면 맨 뒤에 추가합니다.

알고리즘 단계

이를 위해 다음과 같은 단계를 따릅니다 −

n > 0인 경우,
- s := n을 문자열로 변환
- k := 빈 문자열
- c := False
- s의 각 문자 i에 대해 반복:
  - i < 5이고 c가 False이면:
    - k := k에 "5"와 i를 이어 붙임
    - c := True
  - 그렇지 않으면:
    - k := k에 i를 이어 붙임
- k를 정수로 변환하여 반환
n ≤ 0인 경우,
- k := 빈 문자열
- s := |n|을 문자열로 변환
- c := False
- s의 각 문자 i에 대해 반복:
  - i > 5이고 c가 False이면:
    - k := k에 "5"와 i를 이어 붙임
    - c := True
  - 그렇지 않으면:
    - k := k에 i를 이어 붙임
- c가 False이면:
  - k := k에 "5"를 이어 붙임
(-k)를 반환

예제

아래 구현을 통해 더 잘 이해해 보겠습니다.

def solve(n):
   if n > 0:
      s = str(n)
      k = ""
      c = False
      for i in s:
         if int(i) < 5 and c == False:
            k += "5" + i
            c = True
         else:
            k += i
      return int(k)
   else:
      k = ""
      s = str(abs(n))
      c = False
      for i in s:
         if int(i) > 5 and c == False:
            k += "5" + i
            c = True
         else:
            k += i
      if not c:
          k += "5"
      return int("-" + k)

n = 834
print(solve(n))