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

문제 풀이 아이디어

Two Pointer

이 문제를 처음 봤을 때는 gems를 dfs 등을 사용해서 gems 내에 모든 범위를 구하고 그 범위가 주어진 조건에 부합하는지 확인하는 방법을 생각했습니다만, gems 배열의 크기가 최대 100,000입니다. 따라서 무조건 O(N) 이하의 시간복잡도를 가지는 알고리즘을 사용해서 풀어야 합니다. 즉 gems를 1번만 순회할 수 있습니다.

다행히도 gems에서 구할 수 있는 경우의 수를 따질 때 중간에 끊어지는 경우 없이 연속된 범위를 다루게 됩니다. 따라서 연속된 범위를 다루는 문제 + O(N) 일 때 유용하게 사용할 수 있는 Two Pointer를 사용해서 풀어보겠습니다.

Dictionary

그리고 보석의 종류가 모두 포함이 되는지 확인할 때도 O(1)의 알고리즘을 사용해야 합니다. 따라서 gems[start…end]를 순환하는 방법이 아니라 Dictionary를 따로 구현해두고 해당 Dictionary를 통해서 확인하도록 하겠습니다.

주의할 점

Two Pointer를 위 문제에서 적용할 때 주의할 점은 0 ~ 0 범위 (=맨 처음 1개의 보석만을 포함하는 범위)를 포함해야 한다는 것입니다. 만약에 start와 end를 모두 0으로 설정하면 반복문 내에서 0 ~ 0 범위에 모든 보석이 포함된 경우에는 (= 1가지의 보석만으로 이루어진 배열인 경우) 원하는 정답을 구할 수 없습니다.

따라서 아래 코드에서는 end를 -1로 설정해두고 첫 반복문을 돌고 다음 반복문에서 0 ~ 0 범위에 대한 판정을 할 수 있도록 했습니다.

코드

func solution(_ gems:[String]) -> [Int] {
    // 보석의 총 갯수
    let gemCount = Set(gems).count
    
    // 현재 범위 (start ~ end)에 어떤 보석이 몇개 있는지
    var dict = [String:Int]()
    
    // 범위의 시작과 끝
    var start = 0
    var end = -1
        //❗️end 0으로 하면 (0 ~ 0)인 경우가 valid인지 판단할 수 없으므로 -1에서 시작
    
    // 범위의 길이 (end - start)의 최솟값을 저장하는 변수
    var min = Int.max
    
    // 정답을 저장하는 배열
    var result = [start + 1, end + 1]
    
    // 모든 종류의 보석이 포함되어 있는지 확인하는 함수
        //👉 dict의 key의 갯수 = 모든 보석의 종류의 갯수와 같으면 true
    func isValid() -> Bool {
        return dict.count == gemCount
    }
    
    while true {
        // 1. valid한 범위인 경우: start + 1
        if isValid() {
            // min 값을 갱신할 수 있다면
            if end - start < min {
                result = [start + 1, end + 1] // 정답 갱신
                min = end - start // min값 갱신
            }
            //✅ start + 1 작업 (dict에서 보석 지우기)
            dict[gems[start]]! -= 1 //👉 dict에서 start에 있던 보석 제거
            //❗️만약에 dict에서 해당 보석의 갯수가 0이 된다면 nil
                //👉 nil로 하지 않으면 dict.count에서 key의 갯수로 잡힘
            if dict[gems[start]]! == 0 {
                dict[gems[start]] = nil
            }
            start += 1
        // 2. valid하지 않은 범위인 경우: end + 1
        } else {
            // end가 끝지점에 도달하면 break
            if end + 1 == gems.count { break }
            // ✅ end + 1 작업 (dict에 보석 추가)
            end += 1
            dict[gems[end], default: 0] += 1
        }
    }

    return result
}