[Algorithm] 보석 쇼핑

[hwangJi-dev]

💬 문제

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

💬 Idea

• 투포인터를 사용하여 싹쓸이할 수 있는 최소구간을 구하자
• leftIndex가 rightIndex보다 작거나 같으면서, rightIndex가 보석의 총 개수 -1 보다 작을 때까지 반복문을 돈다.
• 딕셔너리(map) 구조를 이용하여 모은 보석의 수를 저장한다.
  • 처음에 반복문 안에 배열을 Set해주는 방식으로 구현하니 시간초과가 났었다.
  • 딕셔너리를 활용하여 보석의 개수를 -, + 해주는 방식으로 변경했더니 해결되었다.
• 모은 보석의 개수가 총 보석 개수와 같다면 leftIndex를 + 1 해주며 구간을 좁히며 최소구간을 찾고,
• 총 보석 개수보다 모은 보석 개수가 모자라다면 rightIndex를 + 1 해주며 구간을 넓힌다

💬 풀이

func solution(gems:[String]) -> [Int] {
    var leftIdx = 0
    var rightIdx = 0
    var minDistance = Int.max
    var collectedGems: [String: Int] = [:]
    var ans: [Int] = []
    let gemCnt = Set(gems).count
    
    while leftIdx <= rightIdx && rightIdx < gems.count {
        if collectedGems[gems[leftIdx]] == nil {
            collectedGems[gems[leftIdx]] = 0
            continue
        }
        
        if collectedGems.count == gemCnt {
            if minDistance > rightIdx - leftIdx {
                minDistance = rightIdx - leftIdx
                ans = [leftIdx + 1, rightIdx + 1]
            }
            
            collectedGems[gems[leftIdx]]! -= 1
            
            if collectedGems[gems[leftIdx]] == 0 {
                collectedGems[gems[leftIdx]] = nil
            }
            leftIdx += 1
        } else {
            if collectedGems[gems[rightIdx]] == nil {
                collectedGems[gems[rightIdx]] = 0
            } else {
                collectedGems[gems[rightIdx]]! += 1
                rightIdx += 1
            }
        }
    }
    
    return ans
}