[24/2/7] 숫자 문자열과 영단어

🍄 프로그래머스 문제

프로그래머스 문제 링크

✍🏻 Github

Github 링크

문제 설명

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

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

• 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초

---

문제 풀이

나의 풀이

import Foundation

func solution(_ s:String) -> Int {
    
    var answer = ""
    var s = s
    let word: [String: Int] = ["zero":0, "one":1, "two":2, "three":3, "four":4, "five":5, "six":6, "seven":7 , "eight":8, "nine":9]
    
    while s != "" {
        if s.first!.isLetter {
            if let w3 = word[ String(s.prefix(3)) ] {
                answer += "\(w3)"
                s.removeFirst(3)
            }else if let w4 = word[ String(s.prefix(4)) ] {
                answer += "\(w4)"
                s.removeFirst(4)
            }else if let w5 =  word[ String(s.prefix(5)) ] {
                answer += "\(w5)"
                s.removeFirst(5)
            }
        }else {
            answer += "\(s.first!)"
            s.removeFirst(1)
        }
    }
    return Int(answer) ?? 0
}

문제 해결 방법

우선 문자열에 대응되는 숫자를 딕셔너리를 이용하여 구현하였다.

문자열을 쭉 훑으며 문자이면 사전에 대응되게끔하고, 숫자이면 그대로 저장하도록 구현하였다.

이때 문제점은 숫자영단어의 문자열 갯수가 정해져있지 않아서 3~5개의 문자열을 빼와서 사전과 비교를 하기를 원했는데 이 과정에서 생각하는 시간이 필요했다.
문자열 갯수가 3~5개로 정해져 있으니,
if let 바인딩을 통해 3, 4, 5개의 문자열을 빼내어 사전에 등록되어 있는 key의 value를 저장하도록 하였다.

이 풀이과정의 단점은 문자열이 three 나 seven, eight일 경우엔 s.prefix()와 사전대입을 해봐야해서 시간이 낭비된다는 것이다.

다른 사람 풀이

import Foundation

func solution(_ s:String) -> Int {
    let arr = ["zero","one","two","three","four","five","six","seven","eight","nine"]
    var str = s
    for i in 0..<arr.count {
        str = str.replacingOccurrences(of: arr[i], with: String(i))
    }
    return Int(str)!
}

문제 해결 방법

문자열에 대응되는 숫자를 딕셔너리를 이용하지 않고, 배열의 인덱스 번호를 이용하여 구현하였다.

replacingOccurrences 함수를 이용하여 해당 문자열이 있다면, 인덱스 번호로 바꾸도록 구현하였다.

그렇다면, 위 두 방법의 실행 시간 차이는 얼만큼일까?

실행 시간 비교

• 나의 풀이 테스트 결과

[1] 실행 시간 : 0.00021207332611083984(s)
[2] 실행 시간 : 1.2040138244628906e-05(s)
[3] 실행 시간 : 1.0013580322265625e-05(s)
[4] 실행 시간 : 9.059906005859375e-06(s)
[5] 실행 시간 : 8.940696716308594e-06(s)
[6] 실행 시간 : 7.987022399902344e-06(s)
[7] 실행 시간 : 7.987022399902344e-06(s)
[8] 실행 시간 : 8.940696716308594e-06(s)
[9] 실행 시간 : 8.940696716308594e-06(s)
[10] 실행 시간 : 7.987022399902344e-06(s)
전체 실행 시간 : 0.00029397010803222656(s)

테스트 1 〉	통과 (0.07ms, 16.5MB)
테스트 2 〉	통과 (0.07ms, 16.7MB)
테스트 3 〉	통과 (0.06ms, 16.5MB)
테스트 4 〉	통과 (0.07ms, 16.5MB)
테스트 5 〉	통과 (0.11ms, 16.5MB)
테스트 6 〉	통과 (0.13ms, 16.2MB)
테스트 7 〉	통과 (0.09ms, 16.5MB)
테스트 8 〉	통과 (0.07ms, 16.5MB)
테스트 9 〉	통과 (0.09ms, 16.4MB)
테스트 10 〉	통과 (0.07ms, 16.4MB)

• 다른 사람의 풀이 테스트 결과

[1] 실행 시간 : 0.001188039779663086(s)
[2] 실행 시간 : 2.8014183044433594e-05(s)
[3] 실행 시간 : 1.895427703857422e-05(s)
[4] 실행 시간 : 6.699562072753906e-05(s)
[5] 실행 시간 : 0.00010097026824951172(s)
[6] 실행 시간 : 6.29425048828125e-05(s)
[7] 실행 시간 : 1.800060272216797e-05(s)
[8] 실행 시간 : 1.800060272216797e-05(s)
[9] 실행 시간 : 1.704692840576172e-05(s)
[10] 실행 시간 : 1.704692840576172e-05(s)
전체 실행 시간 : 0.0015360116958618164(s)

테스트 1 〉	통과 (0.28ms, 16.4MB)
테스트 2 〉	통과 (0.20ms, 16.5MB)
테스트 3 〉	통과 (0.18ms, 16.4MB)
테스트 4 〉	통과 (0.19ms, 16.4MB)
테스트 5 〉	통과 (0.20ms, 16.4MB)
테스트 6 〉	통과 (0.29ms, 16.4MB)
테스트 7 〉	통과 (0.22ms, 16.6MB)
테스트 8 〉	통과 (0.22ms, 16.2MB)
테스트 9 〉	통과 (0.22ms, 16.6MB)
테스트 10 〉	통과 (0.11ms, 16.3MB)

밑의 풀이가 더 빠를 줄 예상했는데, 아니었다.

테스트 결과 나의 풀이가 약 5.22배정도 더 빨랐다.

분석해보니 내가 푼 풀이에서는 removeFirst를 통한 시간복잡도가 O(n)이므로 전체 문자열의 count가 n이라고 했을 때, O(n)의 시간이 걸린다.

다른 사람의 풀이에서는 for 문을 arr의 count 만큼 돌고 있어 O(10)만큼의 시간 복잡도가 들어가고, replacingOccurrences 함수가 문자열 s를 전체적으로 탐색하는 시간이 O(n)이 걸리므로, 총 O(10) * O(n) 번이 걸리는 것이다. **replacingOccurrences**를 사용하면 이미 탐색하여 숫자로 바꾼 문자열도 중첩으로 검사하게 되니 시간 복잡도가 더 오래 걸리는 것 같다. 그래도 코드가 아주 깔끔해서 한 눈에 잘 들어온다.

중요한 개념

• replacingOccurrences의 시간복잡도는 O(n), 중첩적으로 문자열을 비교하는 경우엔 시간이 더 오래걸림.
• 문자열과 숫자를 대조할 땐, 배열을 사용할 수도 있음. 하지만, 딕셔너리가 훨씬 빠름.