프로그래머스

프로그래머스 숫자 문자열과 영단어 풀이: 문자열 순차 변환

작성·코드 검증: solve together · 작성 언어: Python

0. 문제 링크와 출처

문자열에 섞여 있는 숫자와 영단어를 구분해 숫자로 바꾸면 되는 문제다. 숫자 단어가 10개로 정해져 있고 입력 길이도 짧아 복잡한 알고리즘이나 자료구조가 필요하지 않으므로 Level 1로 판단한다.

1. 문제 요약

문자열 s에는 숫자 문자와 zero부터 nine까지의 영단어가 섞여 있다. 문자열의 내용을 읽어 원래 숫자로 복원해 반환한다.

예를 들어 다음과 같이 변환한다.

"one4seveneight" -> "1478" -> 1478
"23four5six7"    -> "234567" -> 234567

중요한 조건은 다음과 같다.

  • s의 길이는 1 이상 50 이하다.
  • s는 숫자 문자 또는 영단어로만 이루어진다.
  • 영단어는 zero, one, two, three, four, five, six, seven, eight, nine이다.
  • 변환한 결과를 정수로 반환한다.

문자열 전체를 한 번에 정수로 바꿀 수 없으므로, 이미 숫자인 부분은 그대로 읽고 영단어는 해당 숫자 하나로 바꿔야 한다.

2. 문제 해결에 사용되는 알고리즘이나 자료구조 설명

상태 전이와 경계 처리

문자열의 현재 위치를 index로 두고 왼쪽부터 읽는다.

  1. 현재 문자가 숫자이면 결과 목록에 그대로 추가하고 한 칸 이동한다.
  2. 현재 문자가 숫자가 아니면 현재 위치에서 시작하는 영단어를 찾는다.
  3. 찾은 영단어에 대응하는 숫자를 결과 목록에 추가한다.
  4. 영단어의 길이만큼 index를 이동한다.
  5. 결과 목록을 하나의 문자열로 합친 뒤 정수로 변환한다.

영단어를 한 글자씩 처리하지 않고 단어 전체를 한 번에 소비해야 한다. 예를 들어 three를 발견하면 3을 추가하고 t, h, r, e, e를 각각 다시 검사하지 않는다.

왼쪽부터 숫자 토큰을 구분하는 방법

현재 위치에서 가능한 영단어는 zero부터 nine까지 10개뿐이다. 따라서 각 위치에서 10개의 단어 중 현재 문자열과 일치하는 단어를 찾으면 된다. 입력이 숫자와 올바른 영단어의 연결로 이루어진다는 조건 덕분에 하나를 찾은 뒤 그 길이만큼 이동하면 다음 숫자 조각의 시작 위치에 도착한다.

숫자와 영단어가 섞여 있어도 처리 규칙은 동일하다. 숫자는 한 칸, 영단어는 단어 길이만큼 이동하므로 원래 순서를 그대로 보존할 수 있다.

오답 접근과 반례

문자열을 바로 int(s)로 변환하면 영단어가 포함된 입력에서 오류가 발생한다.

s = "one4"

이 입력의 정답은 14이지만, "one4"는 Python에서 바로 정수로 변환할 수 없다. 숫자 문자만 골라내는 방식도 영단어의 숫자를 놓치므로, 영단어를 대응하는 숫자로 먼저 변환해야 한다.

영단어를 찾은 뒤 첫 글자만 이동하면 다음 순회에서 단어의 나머지 글자를 다시 읽게 된다. 단어를 찾았을 때 len(word)만큼 이동해야 같은 단어를 여러 번 처리하지 않는다.

시간·공간 복잡도

문자열의 각 조각을 왼쪽부터 처리한다. 각 위치에서 확인하는 영단어 수는 10개로 고정되어 있으므로 전체 시간 복잡도는 O(n)이다. 결과 숫자를 저장하는 목록을 제외한 탐색 변수와 단어 표의 크기는 고정되어 있어, 추가 공간 복잡도는 결과를 제외하면 O(1)이다.

3. 문제 해결 코드 (Python)

words는 영단어와 숫자 문자의 대응 관계를 저장한다. digits에는 변환된 숫자 문자를 순서대로 담고, index는 아직 처리하지 않은 문자열의 시작 위치를 가리킨다.

def solution(s):
    words = {
        "zero": "0",
        "one": "1",
        "two": "2",
        "three": "3",
        "four": "4",
        "five": "5",
        "six": "6",
        "seven": "7",
        "eight": "8",
        "nine": "9",
    }
    digits = []
    index = 0

    while index < len(s):
        if s[index].isdigit():
            digits.append(s[index])
            index += 1
            continue

        for word, digit in words.items():
            if s.startswith(word, index):
                digits.append(digit)
                index += len(word)
                break

    return int("".join(digits))

문제 조건상 현재 위치에는 반드시 숫자 또는 영단어가 시작하므로, 영단어를 찾은 뒤 항상 index가 앞으로 이동한다. startswith(word, index)를 사용해 현재 위치에서 단어가 시작하는지 확인하고, 일치한 단어의 길이만큼 이동하는 것이 핵심이다.

복사해 실행할 테스트

아래 검사를 풀이 코드 아래에 붙여 python 파일명.py로 실행하면 숫자와 영단어가 섞인 입력을 확인할 수 있다.

assert solution("one4seveneight") == 1478
assert solution("23four5six7") == 234567
assert solution("oneone") == 11

4. 공식 예제와 추가 검증

작성한 solution 함수를 Python으로 실행해 공식 예제와 숫자·영단어 혼합, 영단어 연결, 숫자만 있는 입력을 확인했다.

공식 예제

입력 기대 출력 확인 결과
"one4seveneight" 1478 통과
"23four5six7" 234567 통과
"2three45sixseven" 234567 통과
"123" 123 통과

추가 검증 1: 처음과 끝이 영단어인 경우

입력: s = "zeroone"
기대 출력: 1
확인 결과: 통과
검증 목적: 문자열 양끝의 영단어를 순서대로 변환하는지 확인

추가 검증 2: 영단어가 연속되는 경우

입력: s = "eighttwo"
기대 출력: 82
확인 결과: 통과
검증 목적: 한 영단어를 처리한 뒤 다음 영단어의 시작 위치로 정확히 이동하는지 확인

추가 검증 3: 숫자와 영단어의 연결

입력: s = "oneeight"
기대 출력: 18
확인 결과: 통과
검증 목적: 영단어 두 개가 공백 없이 이어진 입력을 처리하는지 확인

5. 다른 풀이 방식 검색 및 비교

영단어를 str.replace로 하나씩 치환하는 방식도 이 문제의 고정된 단어 목록에서는 사용할 수 있다. 다만 이 글에서는 현재 위치를 명시적으로 관리하며 숫자는 한 칸, 영단어는 단어 길이만큼 이동하는 과정을 보여주기 위해 순차 스캔을 사용했다.

정규 표현식으로 숫자 단어를 한 번에 찾아 치환하는 방식도 가능하다. 하지만 영단어가 10개로 고정되어 있고 입력 길이가 짧으므로, 사전과 startswith만 사용하는 방식이 별도 패턴 문법 없이 문제의 입력 구조를 직접 보여준다.

마무리

숫자 문자열과 영단어는 문자열을 왼쪽부터 읽으며 현재 위치의 숫자 또는 영단어를 숫자 하나로 바꾸면 해결할 수 있다. 영단어를 발견했을 때 단어 전체 길이만큼 이동하면 다음 조각을 놓치지 않고, 결과를 정수로 변환해 반환할 수 있다. 숫자 단어의 종류가 10개로 고정되어 있어 O(n) 시간과 결과를 제외한 O(1) 추가 공간으로 처리된다.

#문자열#프로그래머스#난이도 1