문제 개요
숫자 0부터 9까지의 영어 표기(zero, one, two, ...)가 임의의 순서로 뒤섞여 있는 비어 있지 않은 문자열이 주어집니다. 이 문자열을 분석해 원래 숫자들을 오름차순으로 출력하는 것이 목표입니다.
이 문제에는 다음과 같은 조건이 있습니다.
- 입력은 항상 유효하며, 반드시 원래 숫자들로 변환될 수 있습니다. 따라서 "abc"나 "zerone"처럼 잘못된 형태의 입력은 주어지지 않습니다.
- 입력 문자열의 길이는 50,000 미만입니다.
예를 들어 입력이 "fviefuro"라면, five(5)와 four(4)로 이루어진 문자열이므로 출력은 "45"가 됩니다.
접근 방법: 고유 문자 기반 카운팅
이 문제의 핵심은 각 영어 숫자 단어에 고유하게 등장하는 문자를 찾아내는 것입니다. 특정 문자가 하나의 숫자 단어에만 나타난다면, 그 문자의 등장 횟수만 세면 해당 숫자의 개수를 바로 알 수 있습니다.
- 'z'는 zero에만 등장 → 0의 개수 확인 가능
- 'w'는 two에만 등장 → 2의 개수 확인 가능
- 'g'는 eight에만 등장 → 8의 개수 확인 가능
- 'x'는 six에만 등장 → 6의 개수 확인 가능
이렇게 먼저 확정된 숫자들의 정보를 활용하면, 나머지 숫자들도 차감(deduction) 방식으로 계산할 수 있습니다. 예를 들어 's'는 six와 seven 양쪽에 등장하므로, 전체 's' 개수에서 six의 개수를 빼면 seven의 개수가 됩니다. 같은 원리로 다른 숫자들도 순서대로 유도할 수 있습니다.
알고리즘 단계
- 0부터 9까지의 영어 단어를 담은 배열 nums를 준비합니다.
- 크기 10의 카운트 배열 cnt를 만듭니다.
- 문자열을 한 번 순회하면서 고유 문자를 만날 때마다 해당 숫자의 카운트를 증가시킵니다.
- s[i] == 'z' → cnt[0]++
- s[i] == 'w' → cnt[2]++
- s[i] == 'g' → cnt[8]++
- s[i] == 'x' → cnt[6]++
- s[i] == 'v' → cnt[5]++
- s[i] == 'o' → cnt[1]++
- s[i] == 's' → cnt[7]++
- s[i] == 'f' → cnt[4]++
- s[i] == 'h' → cnt[3]++
- s[i] == 'i' → cnt[9]++
- 이미 확정된 숫자 정보를 이용해 나머지 카운트를 보정합니다.
- cnt[7] -= cnt[6] ('s'는 six와 seven에 공통 등장)
- cnt[5] -= cnt[7] ('v'는 seven과 five에 공통 등장)
- cnt[4] -= cnt[5] ('f'는 five와 four에 공통 등장)
- cnt[1] -= (cnt[2] + cnt[4] + cnt[0]) ('o'는 two, four, zero에도 등장)
- cnt[3] -= cnt[8] ('h'는 three와 eight에 공통 등장)
- cnt[9] -= (cnt[5] + cnt[6] + cnt[8]) ('i'는 five, six, eight에도 등장)
- 각 숫자의 카운트만큼 해당 숫자를 정답 문자열에 추가합니다.
- 정답 문자열을 반환합니다.
이 방식은 문자열을 딱 두 번(순회 1회 + 결과 생성) 처리하므로 시간 복잡도는 O(n)이며, 길이가 최대 50,000인 입력에서도 매우 효율적으로 동작합니다.
C++ 구현 예제
아래 코드를 통해 실제 구현을 확인해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string originalDigits(string s) {
string nums[]= {"zero", "one", "two", "three", "four", "five", "six", "seven","eight", "nine"};
vector <int> cnt(10);
string ans = "";
int n = s.size();
for(int i = 0; i < n; i++){
if(s[i] == 'z')cnt[0]++;
if(s[i] == 'w') cnt[2]++;
if(s[i] == 'g')cnt[8]++;
if(s[i] == 'x')cnt[6]++;
if(s[i] == 'v')cnt[5]++;
if(s[i] == 'o')cnt[1]++;
if(s[i] == 's')cnt[7]++;
if(s[i] == 'f')cnt[4]++;
if(s[i] == 'h')cnt[3]++;
if(s[i] == 'i') cnt[9]++;
}
cnt[7] -= cnt[6];
cnt[5] -= cnt[7];
cnt[4] -= cnt[5];
cnt[1] -= (cnt[2] + cnt[4] + cnt[0]);
cnt[3] -= cnt[8];
cnt[9] -= (cnt[5] + cnt[6] + cnt[8]);
for(int i = 0; i < 10; i++){
for(int j = 0; j < cnt[i]; j++){
ans += (char)(i + '0');
}
}
return ans;
}
};
main(){
Solution ob;
cout << ob.originalDigits("fviefuro");
}입력
"fviefuro"
출력
"45"
마무리
이 문제는 무작정 모든 조합을 탐색하는 대신, 각 숫자 단어의 철자적 특성을 관찰하면 선형 시간 안에 해결할 수 있다는 점에서 흥미롭습니다. 고유 문자로 시작 숫자들을 확정하고, 공유되는 문자는 차감 방식으로 정리하는 패턴은 유사한 문자 카운팅 문제에서도 널리 활용되는 기법이니 꼭 기억해 두시길 바랍니다.