[ 프로그래머스 ] 옹알이(2)

 

 

 

🍄 코딩테스트

코딩테스트 문제 풀이

✍🏻 Github

문제 풀이 github 링크

 

---

 

문제 설명

머쓱이는 태어난 지 11개월 된 조카를 돌보고 있습니다. 조카는 아직 "aya", "ye", "woo", "ma" 네 가지 발음과 네 가지 발음을 조합해서 만들 수 있는 발음밖에 하지 못하고 연속해서 같은 발음을 하는 것을 어려워합니다. 문자열 배열 babbling이 매개변수로 주어질 때, 머쓱이의 조카가 발음할 수 있는 단어의 개수를 return하도록 solution 함수를 완성해주세요.

 

제한사항

• 1 ≤ babbling의 길이 ≤ 100
• 1 ≤ babbling[i]의 길이 ≤ 30
• 문자열은 알파벳 소문자로만 이루어져 있습니다.

 

입출력 예

babbling result

babbling	result
["aya", "yee", "u", "maa"]	1
["ayaye", "uuu", "yeye", "yemawoo", "ayaayaa"]	2

 

입출력 예 설명

입출력 예 #1

• ["aya", "yee", "u", "maa"]에서 발음할 수 있는 것은 "aya"뿐입니다. 따라서 1을 return합니다.

입출력 예 #2

• ["ayaye", "uuu", "yeye", "yemawoo", "ayaayaa"]에서 발음할 수 있는 것은 "aya" + "ye" = "ayaye", "ye" + "ma" + "woo" = "yemawoo"로 2개입니다. "yeye"는 같은 발음이 연속되므로 발음할 수 없습니다. 따라서 2를 return합니다.

 

유의사항

• 네 가지를 붙여 만들 수 있는 발음 이외에는 어떤 발음도 할 수 없는 것으로 규정합니다. 예를 들어 "woowo"는 "woo"는 발음할 수 있지만 "wo"를 발음할 수 없기 때문에 할 수 없는 발음입니다.

 

---

 

 

문제 풀이

나의 풀이

import Foundation

func solution(_ babbling:[String]) -> Int {
    
    // 아기가 조합할 수 있는 옹알이의 개수
    var count = 0
    // 아기가 할 수 있는 옹알이
    let word = [ "aya", "ye", "woo", "ma"]
    
    for bab in babbling {
    
        var bab = bab
        // 반복되는 문자열을 찾기위한 문자열 저장
        var pre: String = ""
        
        while true {
            if bab.count < 2 {
                break
            }else if bab.count == 2 {
                let bab2 = String(bab.prefix(2))
                if word.contains(bab2) && bab2 != pre {
                    pre = bab2
                    bab.removeFirst(2)
                }else {
                    break
                }
            }else {
                let bab2 = String(bab.prefix(2))
                let bab3 = String(bab.prefix(3))
                
                if word.contains(bab2) && bab2 != pre {
                    pre = bab2
                    bab.removeFirst(2)
                }else if word.contains(bab3) && bab3 != pre {
                    pre = bab3
                    bab.removeFirst(3)
                }else {
                    break
                }
            }
            
            if bab == "" {
                count += 1
                break
            }

        }
    }
    return count
}

 

우선적으로 두 가지에 집중해서 풀었다.

1. 문자열이 반복이 되면 문자열 비교 종료
2. 문자열 개수에 따른 출력

 

아기가 낼 수 있는 babbling이 4가지 밖에 되지 않고 소리의 개수가 2개 아니면 3개이다.

이를 이용해 babbling의 앞에 2개나 3개의 문자를 꺼내서 ( prefix 사용 )

아기가 낼 수 있는 babbling에 포함이 되거나 중복이 되지 않는다면 해당 문자를 삭제하고 다시 반복문을 돌도록 풀었다.

 

여기서 문자열이 3개 이상이면, prefix(2), prefix(3)을 모두 반환하여 비교할 수 있는데

문자열이 2개 이상이면, prefix(3)을 반환할 수 없어서 에러가 날 것이다.

 

그래서 따로 함수를 만들려다 조건문으로 구성을 했다.

 

문자열이 2개보다 작다면 반복문 종료

문자열의 길이가 2개라면 prefix(2)로 비교

문자열의 길이가 3개라면 prefix(3)과 prefix(2) 둘다 비교

 

실행하였을 때의 시간이다.

테스트 1 〉	통과 (0.07ms, 16.4MB)
테스트 2 〉	통과 (0.06ms, 16.4MB)
테스트 3 〉	통과 (0.09ms, 15.8MB)
테스트 4 〉	통과 (0.06ms, 16MB)
테스트 5 〉	통과 (0.05ms, 16.2MB)
테스트 6 〉	통과 (0.05ms, 16.4MB)
테스트 7 〉	통과 (0.04ms, 16.5MB)
테스트 8 〉	통과 (0.07ms, 16.1MB)
테스트 9 〉	통과 (0.07ms, 16.3MB)
테스트 10 〉	통과 (0.05ms, 16.2MB)
테스트 11 〉	통과 (0.10ms, 16MB)
테스트 12 〉	통과 (0.47ms, 16.2MB)
테스트 13 〉	통과 (0.49ms, 16.2MB)
테스트 14 〉	통과 (0.53ms, 16.1MB)
테스트 15 〉	통과 (0.27ms, 16.4MB)
테스트 16 〉	통과 (0.24ms, 16.2MB)
테스트 17 〉	통과 (0.84ms, 16.5MB)
테스트 18 〉	통과 (0.34ms, 16.2MB)
테스트 19 〉	통과 (0.07ms, 16.1MB)
테스트 20 〉	통과 (0.16ms, 16.4MB)

 

여러 조건문으로 코드가 복잡하게 짜여진거 같아 정리를 하고 싶었지만 불가능.. ㅎ

그래도 최대한 시간을 덜 쓰기 위해서 반복문을 빠져나갈 수 있는 조건을 많이 만들어두었다.

 

 

다른 사람 풀이

첫번째,

import Foundation

func solution(_ babbling:[String]) -> Int {
    var count: Int = 0
    for element in babbling {
        var str = String(element)
        str = str.replacingOccurrences(of: "aya", with: "1")
        str = str.replacingOccurrences(of: "ye", with: "2")
        str = str.replacingOccurrences(of: "woo", with: "3")
        str = str.replacingOccurrences(of: "ma", with: "4")
        if Int(str) != nil && !str.contains("11") && !str.contains("22") && !str.contains("33") && !str.contains("44"){
            count += 1
        }
    }    
    return count
}

 

이 분의 풀이는 replacingOccurrences를 이용하였다.

반복문을 돌리지 않고 포함이 되어있는 문자열을 한번에 바꿀 수 있어 좋은 코드인것 같고,

' 문자열 대체는 replacingOccurrences '인데 왜 생각해내지 못했나 라는 자기 반성도 하게 된다.

이 분은 반복문자열을 제거하는 방법으로 if문의 조건을 나열하였는데, 이 부분도 좋은 것 같다.

 

다만 시간을 봤을 때,

테스트 1 〉	통과 (0.45ms, 16.4MB)
테스트 2 〉	통과 (0.27ms, 16.4MB)
테스트 3 〉	통과 (0.42ms, 16.4MB)
테스트 4 〉	통과 (0.32ms, 16.3MB)
테스트 5 〉	통과 (0.27ms, 16.6MB)
테스트 6 〉	통과 (0.26ms, 16.3MB)
테스트 7 〉	통과 (0.38ms, 16.3MB)
테스트 8 〉	통과 (0.38ms, 16.5MB)
테스트 9 〉	통과 (0.48ms, 16.4MB)
테스트 10 〉	통과 (0.31ms, 16.3MB)
테스트 11 〉	통과 (0.57ms, 16.3MB)
테스트 12 〉	통과 (1.90ms, 16.6MB)
테스트 13 〉	통과 (2.08ms, 16.6MB)
테스트 14 〉	통과 (1.79ms, 16.4MB)
테스트 15 〉	통과 (3.33ms, 16.4MB)
테스트 16 〉	통과 (2.13ms, 16.5MB)
테스트 17 〉	통과 (2.69ms, 16.5MB)
테스트 18 〉	통과 (3.69ms, 16.6MB)
테스트 19 〉	통과 (0.82ms, 16.5MB)
테스트 20 〉	통과 (1.52ms, 16.4MB)

 

replacingOccurences의 시간 복잡도가 O(n)이므로

대략적으로 배열 하나당 시간복잡도의 최대가 O(n) * 4 일 것이다. ( n은 문자열 길이 )

여기서 babbling의 배열의 개수 만큼 반복이 되니

• 1 ≤ babbling의 길이 ≤ 100
• 1 ≤ babbling[i]의 길이 ≤ 30

이 부분을 확인했을 때, 이분의 시간복잡도의 최대값은 100 * ( O(30) * 4 ) 이다.

 

이 문제에서는 문자열을 대체하여 푸는 방법이 시간적으로는 효율적이지 못한 것 같다.

 

 

두 번째,

import Foundation

func solution(_ babbling:[String]) -> Int {
    let strArr = ["aya", "ye", "woo", "ma"]

    var answer = 0
    func checkWord(_ str: String) -> Bool {
        var b = str

        for s in strArr {
            b = b.replacingOccurrences(of: s, with: "-")
            if b.contains("--") { return false }
            b = b.replacingOccurrences(of: "-", with: " ")

        }

        return b.replacingOccurrences(of: " ", with: "").isEmpty
    }

    for babble in babbling {
        if checkWord(babble) {
            answer += 1
        }
    }

    return answer
}

 

이 분은 위에 분과 동일하게 replacingOccurrences를 사용하였지만,

반복문을 두 번 돌리면서 반복되는 문자열이 나오는 즉시 반복문을 종료하도록 하였다.

 

다만, 문자열이 반복이 된다면 문자열 종료가 된다는 게 있으나 문자열을 비교하는 과정에서 -로 바꾸고 반복이 되지 않는다면 다시 “ “로 바꾸는 부분이 필요치 않게 replacingOccurences의 함수를 많이 사용한다고 생각하였다. 

테스트 1 〉	통과 (0.31ms, 16.5MB)
테스트 2 〉	통과 (0.37ms, 16.2MB)
테스트 3 〉	통과 (0.40ms, 16.4MB)
테스트 4 〉	통과 (0.25ms, 16.2MB)
테스트 5 〉	통과 (0.29ms, 16.3MB)
테스트 6 〉	통과 (0.27ms, 16.5MB)
테스트 7 〉	통과 (0.25ms, 16.5MB)
테스트 8 〉	통과 (0.28ms, 16.5MB)
테스트 9 〉	통과 (0.46ms, 16.5MB)
테스트 10 〉	통과 (0.48ms, 16.4MB)
테스트 11 〉	통과 (0.50ms, 16.4MB)
테스트 12 〉	통과 (2.46ms, 16.5MB)
테스트 13 〉	통과 (6.67ms, 16.4MB)
테스트 14 〉	통과 (3.50ms, 16.6MB)
테스트 15 〉	통과 (2.53ms, 16.4MB)
테스트 16 〉	통과 (7.09ms, 16.6MB)
테스트 17 〉	통과 (4.47ms, 16.6MB)
테스트 18 〉	통과 (4.78ms, 16.5MB)
테스트 19 〉	통과 (1.11ms, 16.3MB)
테스트 20 〉	통과 (2.24ms, 16.4MB)

 

 

 

세 번째,

func solution(_ babbling: [String]) -> Int {
    return babbling.filter { $0.range(of: "^(aya(?!aya)|ye(?!ye)|woo(?!woo)|ma(?!ma))+$", options: .regularExpression) != nil }.count
}

 

사실 이 분꺼는 코드 리뷰가 하기 싫었지만, 시간이 궁금하기 때문에 해보려고 한다.

( 저 코드에 babbling 대신에 OO소리라고 욕이 적혀있었음.. 인성.. )

 

regularExpression이라는 정규표현식을 사용하여 푸셨다.

사실 시간이 젤 적게 걸릴 줄 알았는데 생각보다 많이 나와서 놀랬다.

 

테스트 1 〉	통과 (1.76ms, 17.9MB)
테스트 2 〉	통과 (1.91ms, 17.8MB)
테스트 3 〉	통과 (1.95ms, 17.6MB)
테스트 4 〉	통과 (1.86ms, 17.8MB)
테스트 5 〉	통과 (1.82ms, 17.7MB)
테스트 6 〉	통과 (2.73ms, 17.9MB)
테스트 7 〉	통과 (1.85ms, 17.7MB)
테스트 8 〉	통과 (1.70ms, 17.7MB)
테스트 9 〉	통과 (1.76ms, 17.6MB)
테스트 10 〉	통과 (1.88ms, 17.8MB)
테스트 11 〉	통과 (1.87ms, 17.6MB)
테스트 12 〉	통과 (2.41ms, 17.6MB)
테스트 13 〉	통과 (2.42ms, 17.7MB)
테스트 14 〉	통과 (2.46ms, 17.9MB)
테스트 15 〉	통과 (3.64ms, 17.6MB)
테스트 16 〉	통과 (2.39ms, 18MB)
테스트 17 〉	통과 (2.54ms, 17.6MB)
테스트 18 〉	통과 (3.59ms, 17.8MB)
테스트 19 〉	통과 (1.95ms, 18.1MB)
테스트 20 〉	통과 (2.22ms, 18.1MB)

 

길이가 짧은 케이스 들에서 속도가 많이 걸리었고, 정규표현식을 사용해서 그런지 대부분의 케이스의 시간이 비슷하게 걸렸다.

 

정규표현식의 패턴에 대한 포스팅도 하나 올려야겠다.

 

 

중요한 개념

• replacingOccurences의 시간복잡도는 O(n)