문제 설명
머쓱이는 태어난 지 11개월 된 조카를 돌보고 있습니다. 조카는 아직 "aya", "ye", "woo", "ma" 네 가지 발음과 네 가지 발음을 조합해서 만들 수 있는 발음밖에 하지 못하고 연속해서 같은 발음을 하는 것을 어려워합니다. 문자열 배열 babbling이 매개변수로 주어질 때, 머쓱이의 조카가 발음할 수 있는 단어의 개수를 return하도록 solution 함수를 완성해주세요.
제한사항
- 1 ≤ babbling의 길이 ≤ 100
- 1 ≤ babbling[i]의 길이 ≤ 30
- 문자열은 알파벳 소문자로만 이루어져 있습니다.
내가 푼 풀이
모든 경우의 수를 순회하는 방법을 이용했는데 주어진 배열의 크기와 문자열의 크기가 작아서 시간초과는 뜨지 않았다.
말할 수 있는 문자의 앞문자를 dictionary에 저장하고 검사했다
1. 말할 수 있는 문자열로 시작하는가?
-> 시작하지 않으면 다음 문장으로 건너뛰기 , 시작하면 계속 검사
2. 만들어진 문자열이 말할 수 있는 문자인가?
-> 말할 수 없는 문자열이라면 계속 순회해서 검사배열에 저장
3. 그 문자가 바로 직전에 말했던 문자인가?
-> 직전의 문자와 다르면 계속 검사, 같다면 말할 수 없는 문자열로 판단
이렇게 문자배열을 모두 돌고 검사하지못한 문자가 있다면 말할 수 없는 문자열로 판단한다.
Swift는 문자열을 다루기 까다로워서 처음에 어떻게 접근할지 막막했다. 이는 내가 String과 관련된 함수를 잘 알고 있지 않아서 그런것도 있고, 문제의 정답을 돌고돌아서 맞춘느낌이 컸다. String관련된 함수를 숙지해두자.
문제 6번이 한번 시간초과가 떴었는데, 반복문 구조는 같지만 알고리즘이 틀렸을때는 시간초과가 뜨지않아서 시간을 좀 줄일 방법을 생각했다.
순회중 검사를 위한 checkArr 배열이 문자로 만들었을때 말할 수 있다면 checkArr배열을 비워야하는데 removeAll() 함수를 사용했었다.
removeAll()은 O(N) 만큼 걸린다. 그래서 checkArr = [] 로 아예 빈 배열로 지정했더니 시간초과가 뜨지않았다.
import Foundation
func solution(_ babbling:[String]) -> Int {
var talk = babbling
var strArr = ["aya", "ye", "woo", "ma"]
var dict: [String: Int] = ["a": 0, "y": 1, "w": 2, "m": 3]
var result = 0
for i in 0..<talk.count { // 모든 문자열 순회
var strs = talk[i].map{String($0)}
var idx = 0
var number = -1 // 말할 수 있는 문자열 번호
var canTalk = true
var prevStr = "" //바로 이전에 말했던 문자열
var checkArr = [String]()
while idx < strs.count { // 문자열 순회
if number == -1 { // 문자의 첫문자 검사
if dict[strs[idx]] == nil { // 발음 가능한 문자열로 시작하는지 검사
canTalk = false
break
} else {
number = dict[strs[idx]]!
}
}
checkArr.append(strs[idx])
var str = checkArr.joined(separator: "")
if strArr.contains(str) { // 문자를 추가한 후 그 문자열이 발음가능한지 검사
if prevStr == str { // 이전에 말했던 문자열인지 검사
canTalk = false
break
} else { // 새로운 발음 가능한 문자라면 이전문자갱신
prevStr = str
checkArr = []
number = -1
}
}
idx += 1
}
if canTalk && checkArr.isEmpty { // 발음 가능한 문자열로 이루어졌는지, 중간에 발음이 불가능한 문자가 섞였는지 확인
result += 1
}
}
return result
}
