안녕하세요 !
https://programmers.co.kr/learn/courses/30/lessons/67258
풀이
투포인터를 이용한 start와 end 인덱스로 문제를 풉니다.
- 보석 종류를
key
로, 그 보석 종류가 몇 번 나왔는지를value
로 저장하는 countDict를 만듭니다.countDict == kinds
인 경우
1) 답을 구할수 있는 경우이므로 start와 end의 차이값이 minDiff 보다 작다면 answer에 저장합니다.
2) 앞부분을 제거해봅니다. 즉, gems[start]의 값을 제거해보고 제거해보았더니 그 보석이 등장한 수가 0이라면
countDict에서 제거해줍니다. (Dictionary에서 key 값을 제거할 때는 nil을 넣어주면 됩니다.)
3) 앞부분을 제거했으니start++
을 해줍니다.countDict != kinds
인 경우 (즉, countDict < kinds)
countDict가 완성이 안된 경우이므로 뒷부분을 확장시켜서 추가해줍니다.
뒷부분을 추가해주는 경우이니까end++
을 해줍니다.
import Foundation
func solution(_ gems:[String]) -> [Int] {
let kinds = Set(gems).count // 보석 종류의 수
if kinds == 1 {
return [1, 1]
}
var countDict: [String: Int] = [:]
var start = 0
var end = 0
var minDiff = Int.max
var answer = [0, 0]
while end < gems.count {
if let _ = countDict[gems[start]] { // gems[start] key 값이 존재한다면
if countDict.count == kinds { // 보석 종류 수랑 같다면
if end - start < minDiff { // 차이 구함
minDiff = end - start
answer[0] = start + 1
answer[1] = end + 1
}
// 앞부분 제거
countDict[gems[start]]! -= 1
if countDict[gems[start]] == 0 {
countDict[gems[start]] = nil
}
start += 1
} else { // 보석 종류 수랑 같지 않으면 끝부분 추가
if let _ = countDict[gems[end]]{
countDict[gems[end]]! += 1
end += 1
} else {
countDict[gems[end]] = 0
}
}
} else { // gems[start] key 값이 없다면 value가 0인 걸로 만들어줌
countDict[gems[start]] = 0
}
}
return answer
}