문제 정의
하나의 숫자 n이 주어졌을 때, 모든 자릿수가 홀수로 이루어진 숫자 중에서 n과 가장 가까운 값을 찾아야 합니다. 만약 두 후보 값이 n과의 거리가 같다면, 그중 더 큰 값을 반환합니다.
예를 들어 입력이 n = 243이라면 출력은 199가 됩니다.
접근 방법
이 문제는 다음 단계를 따라 해결할 수 있습니다.
- 첫 번째 짝수 자릿수 찾기: n을 문자열로 변환한 뒤 왼쪽부터 스캔하여 처음 등장하는 짝수 자릿수의 위치(first_even)를 기록합니다.
- 조기 반환: 짝수 자릿수가 하나도 없다면(first_even이 -1이면) 이미 모든 자릿수가 홀수이므로 n을 그대로 반환합니다.
- 큰 후보(big) 계산: 첫 짝수 자릿수까지의 접두사에 1을 더한 값 뒤에, 남은 자릿수 개수만큼 '1'을 이어 붙여 n보다 큰 최소 후보를 만듭니다.
- 작은 후보(small) 계산: 첫 짝수 자릿수의 값에 따라 분기합니다.
- 자릿수가 '0'이고 바로 앞 자릿수가 '1'이면, 접두사 전체에서 1을 뺍니다.
- 자릿수가 '0'이지만 앞 자릿수가 '1'이 아니면, 자릿수 값에서 11을 빼 자리내림을 처리합니다.
- 그 외의 경우에는 접두사에서 1을 뺍니다.
- 거리 비교: d1 = n − small, d2 = big − n을 계산합니다. d1이 더 작으면 small을 반환하고, 그렇지 않으면(d1 ≥ d2) big을 반환합니다. 거리가 같을 때는 더 큰 값인 big이 선택됩니다.
파이썬 구현 코드
class Solution:
def solve(self, n):
first_even = -1
s = str(n)
l = len(s)
for i in range(l):
if int(s[i]) % 2 == 0:
first_even = i
break
if first_even == -1:
return n
big = str(int(s[: i + 1]) + 1)
if s[i] == "0":
if s[i - 1] == "1":
small = str(int(s[: i + 1]) - 1)
else:
small = str(int(s[i : i + 1]) - 11)
else:
small = str(int(s[: i + 1]) - 1)
for i in range(i + 1, l):
big += "1"
small += "9"
big, small = int(big), int(small)
d2 = big - n
d1 = n - small
if d1 < d2:
return small
elif d1 >= d2:
return big
ob = Solution()
n = 243
print(ob.solve(n))
입력
243
출력
199
동작 과정 상세 분석 (n = 243)
n = 243일 때 코드가 실제로 어떻게 동작하는지 단계별로 살펴보겠습니다.
- 문자열 "243"에서 첫 번째 짝수 자릿수는 인덱스 0의 '2'입니다.
- big: 접두사 "2"에 1을 더해 "3"이 된 뒤, 남은 2자리에 '1'을 붙여 311이 됩니다.
- small: 접두사 "2"에서 1을 빼 "1"이 된 뒤, 남은 2자리에 '9'를 붙여 199가 됩니다.
- 거리 비교: d1 = 243 − 199 = 44, d2 = 311 − 243 = 68이므로 d1 < d2 → 199를 반환합니다.
복잡도 분석
n의 자릿수를 d라고 할 때, 각 자릿수를 한 번씩만 스캔하고 문자열을 구성하므로 시간 복잡도는 O(d), 공간 복잡도 역시 O(d)입니다. 즉, 매우 큰 수에 대해서도 효율적으로 동작합니다.