문제 개요
"0"부터 "9"까지의 숫자와 소문자 영어 알파벳으로 이루어진 영숫자(alphanumeric) 문자열 s가 있다고 가정해 봅시다. 우리가 해야 할 일은 문자열 s에 포함된 숫자들의 합을 구하는 것입니다. 이때 연속된 숫자들은 하나의 숫자로 간주한다는 점이 핵심입니다.
예를 들어 입력이 s = "hello25world63power86"이라면, 출력은 174가 됩니다. 25 + 63 + 86 = 174이기 때문입니다.
해결 방법
이 문제는 다음 단계를 따라 해결할 수 있습니다.
- 결과를 저장할 변수 ret과 현재 숫자를 저장할 변수 curr을 각각 0으로 초기화합니다.
- 문자열 s의 각 문자 ch에 대해 다음을 반복합니다.
- ch가 숫자라면 → curr = 10 * curr + int(ch) 로 현재 숫자를 누적합니다.
- 그렇지 않다면(알파벳 등) → 지금까지 쌓인 curr 값을 ret에 더하고, curr을 0으로 초기화합니다.
- 반복이 끝나면 마지막에 남아 있는 curr 값도 더해야 하므로 ret + curr을 반환합니다.
예제 코드
아래 파이썬 구현을 통해 더 잘 이해할 수 있습니다.
from string import digits
def solve(s):
ret = 0
curr = 0
for ch in s:
if ch in digits:
curr = 10 * curr + int(ch)
else:
ret += curr
curr = 0
return ret + curr
s = "hello25world63power86"
print(solve(s))
입력
"hello25world63power86"
출력
174
동작 원리 정리
이 알고리즘의 시간 복잡도는 O(n)으로, 문자열의 길이에 비례하여 한 번만 순회하면 되기 때문에 매우 효율적입니다. 자릿수를 누적할 때 curr = 10 * curr + int(ch) 공식을 사용하면 "25"처럼 두 자리 이상의 연속된 숫자도 하나의 정수로 자연스럽게 만들 수 있다는 점이 핵심 아이디어입니다.