문제 설명
소문자 영숫자(alphanumeric)로 이루어진 문자열 s가 주어졌다고 가정해 봅시다. 문자열에서 숫자가 아닌 모든 문자를 공백으로 바꾸면, 하나 이상의 공백으로 구분된 여러 개의 정수가 남게 됩니다. 우리가 구해야 하는 것은 이러한 치환 작업을 수행한 후 문자열에 존재하는 서로 다른 정수의 개수입니다.
여기서 두 숫자가 '다르다'고 판단하는 기준은, 선행 0(leading zero)을 제외한 십진수 표현이 서로 다른 경우입니다. 즉, "012"와 "12"는 문자열로는 다르지만 정수로는 같은 값이므로 동일한 숫자로 취급됩니다.
예시
입력이 s = "ab12fg012th5er67"라고 해봅시다. 숫자가 아닌 문자를 제거하면 ["12", "012", "5", "67"]이라는 네 개의 숫자가 추출됩니다. 하지만 "12"와 "012"는 정수로는 같은 값이므로, 최종 결과는 3이 됩니다.
접근 방법
이 문제는 문자열을 한 번 순회하면서 연속된 숫자들을 그룹으로 묶은 뒤, 정수로 변환하여 중복을 제거하는 방식으로 해결할 수 있습니다. 단계별 과정은 다음과 같습니다.
- 정수를 저장할 리스트
nums와 임시 문자열k(빈 문자열로 초기화)를 준비합니다. - 문자열 s의 각 문자를 순회하면서, 해당 문자의 ASCII 코드가 47보다 크고 58보다 작으면(즉, '0'~'9' 사이의 숫자 문자이면)
k에 이어 붙입니다. - 숫자가 아닌 문자를 만나면, 지금까지 쌓인
k가 비어 있지 않은 경우 이를 정수로 변환하여nums에 추가하고k를 초기화합니다. - 순회가 끝난 후에도
k가 비어 있지 않다면, 마지막 숫자 덩어리이므로 정수로 변환해nums에 추가합니다. set()을 이용해nums의 중복을 제거한 뒤, 고유한 요소의 개수를 반환합니다.
구현 코드
아래 예제를 통해 더 자세히 살펴보겠습니다.
def solve(s):
nums = []
k = ""
for i in range(len(s)):
if ord(s[i]) > 47 and ord(s[i]) < 58:
k += s[i]
else:
if(k != ""):
nums.append(int(k))
k = ""
if(k != ""):
nums.append(int(k))
return len(set(nums))
s = "ab12fg012th5er67"
print(solve(s))
입력
"ab12fg012th5er67"
출력
3
동작 원리 및 복잡도 분석
이 코드에서 핵심 역할을 하는 것은 ord() 함수입니다. ord(s[i])는 문자의 ASCII 코드 값을 반환하며, 숫자 문자 '0'부터 '9'까지의 ASCII 코드는 각각 48부터 57 사이입니다. 따라서 조건식 ord(s[i]) > 47 and ord(s[i]) < 58은 해당 문자가 숫자인지 판별하는 기준이 됩니다.
문자열 전체를 한 번만 순회하므로 시간 복잡도는 O(n)이며, 숫자 덩어리를 저장하는 리스트와 집합에 필요한 공간 복잡도 역시 O(n) 수준입니다.
참고로, 파이썬의 re 모듈을 활용하면 정규 표현식 re.findall(r'\d+', s)로 숫자 덩어리를 손쉽게 추출한 뒤 int()로 변환하여 집합에 담는 방식으로도 동일한 결과를 얻을 수 있습니다.