숫자 n이 주어졌을 때, 이 숫자의 어느 위치에든 5를 한 번 삽입하여 만들 수 있는 최댓값을 찾는 문제입니다.
예를 들어 입력이 n = 826이라면, 5를 첫 번째 자리 뒤에 삽입한 8526이 만들 수 있는 값 중 가장 큽니다.
해결 접근 방법
이 문제는 숫자를 문자열로 다루면 간단하게 해결할 수 있습니다. 핵심 아이디어는 5를 삽입할 수 있는 모든 위치를 시도해 보고, 그중 가장 큰 값을 선택하는 완전 탐색 방식입니다. 단계별로 살펴보겠습니다.
- temp := n을 문자열로 변환한 값
- ans := 음의 무한대(-inf)로 초기화
- i를 0부터 temp의 길이까지 반복하며 다음을 수행합니다.
- cand := temp의 처음부터 i번째 앞까지의 부분 문자열 + '5' + 나머지 부분 문자열을 이어 붙인 값
- 만약 i가 0이고 temp[0]이 '-'라면, 부호 앞에 5를 삽입하는 것은 유효하지 않으므로 다음 반복으로 건너뜁니다.
- ans := ans와 int(cand) 중 더 큰 값으로 갱신
- 모든 반복이 끝나면 ans를 반환합니다.
음수가 입력된 경우에도 부호 앞에 삽입하는 경우만 제외하고 모든 위치를 시도하기 때문에 올바른 결과를 얻을 수 있습니다. 시간 복잡도는 자릿수를 d라고 할 때 O(d²)이며, d는 일반적으로 매우 작기 때문에 충분히 효율적입니다.
구현 예제
다음 파이썬 코드를 통해 더 잘 이해할 수 있습니다.
class Solution:
def solve(self, n):
temp = str(n)
ans = float('-inf')
for i in range(len(temp) + 1):
cand = temp[:i] + '5' + temp[i:]
if i == 0 and temp[0] == '-':
continue
ans = max(ans, int(cand))
return ans
ob = Solution()
print(ob.solve(826))
입력
826
출력
8526
동작 원리 요약
입력 826의 경우 5를 삽입할 수 있는 위치는 총 4곳입니다. 각 위치에 삽입했을 때 만들어지는 값은 5826, 8526, 8256, 8265이며, 이 중 가장 큰 값인 8526이 최종 결과로 반환됩니다.