[알고리즘 연습] 보석 쇼핑 (프로그래머스 lv3, 스위프트)

문제

https://programmers.co.kr/learn/courses/30/lessons/67258?language=swift

코딩테스트 연습 - 보석 쇼핑

풀이

func solution(_ gems:[String]) -> [Int] {
    
    var start = 0
    var end = 0
    let totalCount = Set(gems).count
    var gemBox = [String:Int]()
    var answer = [1, gems.count]
    
    while end < gems.count {   
        
        gemBox[gems[end], default: 0] += 1 
        
        while start <= end && gemBox[gems[start]]! > 1 {
            gemBox[gems[start]]! -= 1
            start += 1
        }         
        
        let nowCount = gemBox.count
        
        if totalCount == nowCount &&
        answer[1] - answer[0] > end - start {
            answer = [start+1, end+1]
        } 
        
        end += 1
    }
    
    return answer
}

• 투 포인터 알고리즘을 활용한 문제
• Set(gems).count을 통해 전체 보석개수를 파악하고 이와 같을 경우 값을 비교하여 answer에 기록함
• 현재까지의 보석 개수를 기록하는 dictionary를 만들고 여기에 매번 end좌표의 보석을 넣어줌
• 해당 end좌표에서는 보석들의 중복이 없도록 start좌표를 최대한 늘려줌 (dictionary의 값이 1보다 크면 start를 늘리고 dictionary 내부값을 하나 줄여줌)
• 이러다가 현재 dictionary 지정값이 전체 보석개수와 같다면 값을 확인하여 대입해줌