[leetcode][423] Reconstruct Original Digits from English

문제 : https://leetcode.com/problems/reconstruct-original-digits-from-english/

---

Note 2번에 집중해보면 코드를 더 간결하게 짤 수 있다.

2. Input is guaranteed to be valid and can be trasformed to its original digits. That means invalid inputs such as "abc" or "zerone" are not permitted.

모든 문자는 숫자로 변경될 수 있는 문자라는 뜻이다. 

즉, 0~9 숫자의 알파벳 중에 자신만 고유하게 가지고 있는 문자가 입력 문자열에 있다면 해당 문자는 반드시 나온다는 뜻이다. 

그렇지 않으면 2번 조건에 어긋나기 때문이다.

ex) z~~ -> z는 zero(0)에 밖에 안나타나므로 이 후 문자열에는 ero 가 한 번 이상은 반드시 나올 것이다.

먼저 입력 문자열을 돌며 알파벳 소문자가 나오는 횟수를 배열에 저장한다.

숫자 알파벳에서 고유한 문자를 추출해보면 다음과 같다.

0 : zero -> z

1 : one

2 : two -> w

3 : three

4 : four -> u

5 : five

6 : six -> x 

7 : seven

8 : eight -> g

9 : nine

0, 2, 4, 6, 8은 자신만 가지고 있는 문자가 있다.

따라서 각 유효한 문자가 나온 횟수가 각 숫자가 만들어질 수 있는 수가 된다.

ex) z~~z~~ -> z가 2번 나오면 0은 2개 만들어진다.

그 다음은 나머지 수들로 똑같이 자신만 가지는 문자를 구해본다.

1 : one -> o

3 : three -> t, h, r 중 하나

5 : five -> f

7 : seven -> s

9 : nine

9를 제외하고 1, 3, 5, 7은 유효한 문자를 하나 이상 가지고 있다.

3은 3개나 유효한 문자를 가지고 있는데 이 중 아무거나 선택해도 상관없다.

마찬가지로 각 유효한 문자가 나온 횟수가 각 숫자가 만들어질 수 있는 수가 되는데

이 중 0, 2, 4, 6, 8도 해당 문자들을 가지고 있을 수 있으므로 이 수를 빼준다.

ex) f~~f~u~~ -> f는 2번 나오지만 5가 2개 만들어지지는 않는다. 왜냐하면 u가 한 번 나왔기 때문에 4가 하나 만들어지고 숫자 4에는 f가 있다(four). 즉, f의 개수에 4 개수를 뺀 값이 5의 개수가 된다.

나머지 9는 nine 중 아무수나 구한 뒤 마찬가지로 해당 문자를 가지고 있는 문자들의 수를 빼면 9의 수가 된다.

숫자들이 나올 수 있는 횟수를 모두 구하면 0 부터 9까지 차례대로 각 횟수만큼 문자열에 더해줘서 정답을 만든다.

입력 문자열의 길이를 N이라 하였을 때, 시간복잡도는 O(N).

---

소스코드 : https://gist.github.com/fpdjsns/c06215a0562d1f5d9e094d5acf5c1d6a