[Swift] 프로그래머스(Lv3) - 보석 쇼핑 (2020 카카오 인턴십 )

Kerri·2021년 6월 23일
0

코테

목록 보기
59/67

안녕하세요 !

https://programmers.co.kr/learn/courses/30/lessons/67258

풀이

투포인터를 이용한 start와 end 인덱스로 문제를 풉니다.

  1. 보석 종류를 key로, 그 보석 종류가 몇 번 나왔는지를 value로 저장하는 countDict를 만듭니다.
  2. countDict == kinds 인 경우
    1) 답을 구할수 있는 경우이므로 start와 end의 차이값이 minDiff 보다 작다면 answer에 저장합니다.
    2) 앞부분을 제거해봅니다. 즉, gems[start]의 값을 제거해보고 제거해보았더니 그 보석이 등장한 수가 0이라면
    countDict에서 제거해줍니다. (Dictionary에서 key 값을 제거할 때는 nil을 넣어주면 됩니다.)
    3) 앞부분을 제거했으니 start++ 을 해줍니다.
  3. 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
}
profile
안녕하세요 !

0개의 댓글