🍄 코딩테스트
코딩테스트 문제 풀이
✍🏻 Github
문제 설명
문자열 s가 주어졌을 때, s의 각 위치마다 자신보다 앞에 나왔으면서, 자신과 가장 가까운 곳에 있는 같은 글자가 어디 있는지 알고 싶습니다.
예를 들어, s="banana"라고 할 때, 각 글자들을 왼쪽부터 오른쪽으로 읽어 나가면서 다음과 같이 진행할 수 있습니다.
- b는 처음 나왔기 때문에 자신의 앞에 같은 글자가 없습니다. 이는 -1로 표현합니다.
- a는 처음 나왔기 때문에 자신의 앞에 같은 글자가 없습니다. 이는 -1로 표현합니다.
- n은 처음 나왔기 때문에 자신의 앞에 같은 글자가 없습니다. 이는 -1로 표현합니다.
- a는 자신보다 두 칸 앞에 a가 있습니다. 이는 2로 표현합니다.
- n도 자신보다 두 칸 앞에 n이 있습니다. 이는 2로 표현합니다.
- a는 자신보다 두 칸, 네 칸 앞에 a가 있습니다. 이 중 가까운 것은 두 칸 앞이고, 이는 2로 표현합니다.
따라서 최종 결과물은 [-1, -1, -1, 2, 2, 2]가 됩니다.
문자열 s이 주어질 때, 위와 같이 정의된 연산을 수행하는 함수 solution을 완성해주세요.
제한사항
- 1 ≤
s의 길이 ≤ 10,000s은 영어 소문자로만 이루어져 있습니다.
입출력 예
| s | result |
|---|---|
| "banana" | [-1, -1, -1, 2, 2, 2] |
| "foobar" | [-1, -1, 1, -1, -1, -1] |
입출력 예 설명
- 입출력 예 #1 지문과 같습니다.
- 입출력 예 #2 설명 생략
문제 풀이
나의 풀이
func solution(_ s:String) -> [Int] {
var stack = [String]()
return s.map{ x in
let chr: String = String(x)
if stack == [] || !stack.contains(chr) {
stack.append(chr)
return -1
}else{
let a = stack.count - Int(stack.lastIndex(of: chr)!)
stack.append(chr)
return a
}
}
}stack에 글자를 넣으면서 그 글자가 stack에 포함이 되어있다면, 뒤에서 몇 번째인지 출력하고, stack에 포함이 되어있지않다면, -1을 출력하도록 로직을 짰다.
map과 조건문을 사용하여, 실행시간을 최대한 줄였고, 코드를 간단하게 짜는 것에 초점을 맞추어 풀었다.
풀면서 궁금한게 있다면, 뒤에서 부터 몇 번째의 인덱스인지를 도출해나가는 과정에서 stack.count - Int(stack.lastIndex(of: chr)!) 보다 더 좋은 코드가 있는지 궁금했다.
다른 사람 풀이
func solution(_ s: String) -> [Int] {
var word: [String: Int] = [:]
var result: [Int] = []
for (index, val) in Array(s).map { String($0) }.enumerated() {
if let beforeIndex = word[val] {
result.append(index - beforeIndex)
} else {
result.append(-1)
}
word[val] = index
}
return result
}이 분의 풀이는 Dictionary를 사용하여 풀었다.
Dictionary에 값이 없다면, -1을 반환하고, Dictionary에 [ Character : Index ] 형식으로 저장을 한다.
만약 Dictionary에 값이 존재한다면, 지금의 index에서 Dictionary의 Index 값을 빼준 후, Dictionary는 새로운 Index 값으로 업데이트를 해준다.
나의 풀이는 stack을 쌓았다면, 다른 사람의 풀이에서는 Dictionary에 업데이트를 해주었다.
실행시간을 비교해보니
- 나의 풀이 실행시간
정확성 테스트 테스트 1 〉 통과 (0.06ms, 16.3MB) 테스트 2 〉 통과 (0.45ms, 16.6MB) 테스트 3 〉 통과 (0.44ms, 16.3MB) 테스트 4 〉 통과 (8.31ms, 16.7MB) 테스트 5 〉 통과 (87.90ms, 17.8MB) 테스트 6 〉 통과 (34.33ms, 16.7MB) 테스트 7 〉 통과 (66.40ms, 17.7MB) 테스트 8 〉 통과 (17.31ms, 17MB) 테스트 9 〉 통과 (50.37ms, 17.5MB) 테스트 10 〉 통과 (10.68ms, 16.7MB) 테스트 11 〉 통과 (58.05ms, 17.5MB) 테스트 12 〉 통과 (0.05ms, 16.3MB) 테스트 13 〉 통과 (0.06ms, 16.2MB) 테스트 14 〉 통과 (6.71ms, 16.5MB) 테스트 15 〉 통과 (0.07ms, 16.4MB) 테스트 16 〉 통과 (0.10ms, 16.2MB) 테스트 17 〉 통과 (0.41ms, 16.6MB) 테스트 18 〉 통과 (10.90ms, 16.7MB) 테스트 19 〉 통과 (11.85ms, 16.7MB) 테스트 20 〉 통과 (2.11ms, 16.5MB) 테스트 21 〉 통과 (0.30ms, 16.3MB) 테스트 22 〉 통과 (28.03ms, 17MB) 테스트 23 〉 통과 (2.33ms, 16.4MB) 테스트 24 〉 통과 (3.00ms, 16.6MB) 테스트 25 〉 통과 (8.37ms, 16.4MB) 테스트 26 〉 통과 (1.21ms, 16.6MB) 테스트 27 〉 통과 (3.96ms, 16.5MB) 테스트 28 〉 통과 (3.45ms, 16.7MB) 테스트 29 〉 통과 (0.04ms, 16.3MB) 테스트 30 〉 통과 (67.43ms, 17.5MB) - 다른 사람의 풀이 실행시간
정확성 테스트 테스트 1 〉 통과 (0.08ms, 16.1MB) 테스트 2 〉 통과 (0.14ms, 16.2MB) 테스트 3 〉 통과 (0.14ms, 16.3MB) 테스트 4 〉 통과 (0.68ms, 16.7MB) 테스트 5 〉 통과 (5.94ms, 17.8MB) 테스트 6 〉 통과 (4.44ms, 17MB) 테스트 7 〉 통과 (9.29ms, 17.8MB) 테스트 8 〉 통과 (1.90ms, 16.8MB) 테스트 9 〉 통과 (5.23ms, 17.7MB) 테스트 10 〉 통과 (1.18ms, 16.9MB) 테스트 11 〉 통과 (5.24ms, 17.8MB) 테스트 12 〉 통과 (0.07ms, 16.5MB) 테스트 13 〉 통과 (0.08ms, 16.3MB) 테스트 14 〉 통과 (0.35ms, 16.5MB) 테스트 15 〉 통과 (0.08ms, 16.4MB) 테스트 16 〉 통과 (0.10ms, 16.5MB) 테스트 17 〉 통과 (0.11ms, 16.3MB) 테스트 18 〉 통과 (1.11ms, 16.6MB) 테스트 19 〉 통과 (2.13ms, 16.6MB) 테스트 20 〉 통과 (0.30ms, 16.6MB) 테스트 21 〉 통과 (0.12ms, 16.5MB) 테스트 22 〉 통과 (2.90ms, 16.9MB) 테스트 23 〉 통과 (0.31ms, 16.5MB) 테스트 24 〉 통과 (0.39ms, 16.6MB) 테스트 25 〉 통과 (0.54ms, 16.5MB) 테스트 26 〉 통과 (0.16ms, 16.2MB) 테스트 27 〉 통과 (0.47ms, 16.6MB) 테스트 28 〉 통과 (0.53ms, 16.5MB) 테스트 29 〉 통과 (0.09ms, 16.4MB) 테스트 30 〉 통과 (6.11ms, 18MB)
Dictionary로 푼 다른 사람의 풀이가 훨씬 빨랐다.
이렇게 오늘 하나를 또 배웁니다...!!!!
중요한 개념
-
Dictionary를 업데이트하며 활용하는 방법!
// Dictionary 선언 var word: [String: Int] = [:] // Dictionary에 값이 들어있는지 확인하는 코드 if let beforeIndex = word[val] { // 코드 } // Dictionary 업데이트 ( 값이 없다면 추가, 값이 있다면 업데이트 ) word[val] = index
