You Nicholas

가고 가고 또 가면 알게되고, 행하고 행하고 또 행하게 되면 이루게 된다.

2 분 소요

1. 문제

[level 1] 숫자 문자열과 영단어 - 81301

문제 링크

성능 요약

메모리: 10.3 MB, 시간: 0.02 ms

구분

코딩테스트 연습 > 2021 카카오 채용연계형 인턴십

채점결과


정확성: 100.0
합계: 100.0 / 100.0

문제 설명

img1.png

네오와 프로도가 숫자놀이를 하고 있습니다. 네오가 프로도에게 숫자를 건넬 때 일부 자릿수를 영단어로 바꾼 카드를 건네주면 프로도는 원래 숫자를 찾는 게임입니다.

다음은 숫자의 일부 자릿수를 영단어로 바꾸는 예시입니다.

  • 1478 → "one4seveneight"
  • 234567 → "23four5six7"
  • 10203 → "1zerotwozero3"

이렇게 숫자의 일부 자릿수가 영단어로 바뀌어졌거나, 혹은 바뀌지 않고 그대로인 문자열 s가 매개변수로 주어집니다. s가 의미하는 원래 숫자를 return 하도록 solution 함수를 완성해주세요.

참고로 각 숫자에 대응되는 영단어는 다음 표와 같습니다.

숫자 영단어
0 zero
1 one
2 two
3 three
4 four
5 five
6 six
7 seven
8 eight
9 nine
제한사항
  • 1 ≤ s의 길이 ≤ 50
  • s가 "zero" 또는 "0"으로 시작하는 경우는 주어지지 않습니다.
  • return 값이 1 이상 2,000,000,000 이하의 정수가 되는 올바른 입력만 s로 주어집니다.
입출력 예
s result
"one4seveneight" 1478
"23four5six7" 234567
"2three45sixseven" 234567
"123" 123
입출력 예 설명

입출력 예 #1

  • 문제 예시와 같습니다.

입출력 예 #2

  • 문제 예시와 같습니다.

입출력 예 #3

  • "three"는 3, "six"는 6, "seven"은 7에 대응되기 때문에 정답은 입출력 예 #2와 같은 234567이 됩니다.
  • 입출력 예 #2와 #3과 같이 같은 정답을 가리키는 문자열이 여러 가지가 나올 수 있습니다.

입출력 예 #4

  • s에는 영단어로 바뀐 부분이 없습니다.
제한시간 안내
  • 정확성 테스트 : 10초

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

2. 해결방법 시간복잡도

  1. 스택 O(N^2)
  2. 단순 코딩 O(N)
  3. 단순 코딩 O(1)

3. 문제 해결 및 코드

  • 주석을 참고하면서 이해를 돕습니다.

4. 알고리즘 및 해설

  1. 해당 문제풀이는 참고만 하고 밑에 다른 풀이를 봐주세요!
  2. 문제는 문자열내 숫자가 아닌 문자로 이루어진 영단어를 숫자로 바꾸는 것이다.
  3. 반복문을 통해 해당 값을 도는 동안 만약 숫자일 경우 바로 넣고, 아닌 경우는 해당 값을 스택에 넣었다.
    • 스택에 모든 문자를 하나로 출력했을 때 나오는 값이 사전에 존재한다면, 해당 값을 넣고 스택을 비우는 방식으로 진행했다.
  4. 이후 결과값에 있는 문자를 정수로 변환하여 출력한다.

5. 회고

  • 기존에 어려운 문제들 풀어버릇해서 해당 문제를 너무 복잡하게 생각해 시간복잡도가 너무 올라가버렸다. ```python num_dic = {“zero”:”0”, “one”:”1”, “two”:”2”, “three”:”3”, “four”:”4”, “five”:”5”, “six”:”6”, “seven”:”7”, “eight”:”8”, “nine”:”9”}

def solution(s): answer = s for key, value in num_dic.items(): answer = answer.replace(key, value) return int(answer)


- 위의 방식을 통해 해당 값을 찾고, 변경하면 O(N)으로도 충분히 풀 수 있는 문제이다.

```python
import re
def solution(s):
    s = re.sub('zero', '0', s)
    s = re.sub('one', '1', s)
    s = re.sub('two', '2', s)
    s = re.sub('three', '3', s)
    s = re.sub('four', '4', s)
    s = re.sub('five', '5', s)
    s = re.sub('six', '6', s)
    s = re.sub('seven', '7', s)
    s = re.sub('eight', '8', s)
    s = re.sub('nine', '9', s)
    return int(s)
  • 정규표현식으로 풀면 더 간단하게 시간복잡도를 O(1)로 줄일 수 있다.

참고