[Swift Algorithm] 67258 보석쇼핑 (2020 카카오 인턴십)

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

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

 

풀이방법

처음에는 단순무식하게 Set을 이용해서 

마지막index를 찾고

마지막index부터 처음으로 돌아오면서 모든 보석을 포함하는 구간을 찾는 방법을 사용했지만

 

[1, 2, 2, 3, 1] 이런경우

(시작 위치 1이라고 가정)

[1, 4]가아니라 [3, 5] 가 나와야 정답인 케이스가 있더라구요

처음에 사용한 방법을 이용하면 이런경우를 골라낼수 없기때문에 다른 방법을 생각해야했어요

 

크기제한이 100,000이므로 n^2을 하면 10,000,000,000이므로 시간초과가 될거에요

 

따라서.. 효율적인 알고리즘을 사용해야해요

 

여기서는 

투 포인트 알고리즘을 사용하는데요

2021.04.22 - [iyOmSd/Title: Algorithm풀이] - [Swift Algorithm] 투 포인터 알고리즘

 

저도 처음 들었고 좋은 로직을 가지고있는것 같다고 생각이들었어요

 

 

Set를 이용해서 입력된 보석의 종류의 갯수를 먼저 구하고

딕셔너리를 이용해서 하나씩 보석의 갯수를 더해가면서 모든 보석을 포함하는지 체크했어요

 

모든 보석의 종류가 있다면

firstIndex와 lastIndex의 거리를 저장된 최소거리와 비교하고

firstIndex의 보석을 삭제하고 firstIndex를 뒤로 하나씩 이동하면서 다시 비교하다가

 

모든 보석의 종류가 없다면

lastIndex를 이동하고 lastIndex보석을 넣어주면서 다시 비교했어요

 

 

private func solutionP67258(_ gems:[String]) -> [Int] {
    var lists = Set<String>()
    gems.forEach { lists.update(with: $0) }
        
    let kindCount = lists.count
    
    var lastIndex = 0
    var firstIndex = 0
    var min = [-100_000, 100_000]
    
    var newList: [String: Int] = [:]
    var isEvery: Bool {
        newList.count == kindCount
    }
    
    // 마지막인덱스 위치 지정
    for i in gems.indices {
        newList.updateValue((newList[gems[i]] ?? 0) + 1, forKey: gems[i])
        
        if isEvery {
            lastIndex = i
            break
        }
    }
    
    while lastIndex < gems.count {
        if isEvery {
            let distance = lastIndex - firstIndex + 1
            let minDistance = min[1] - min[0] + 1
            if minDistance > distance {
                min = [firstIndex, lastIndex]
            }
            
            // 처음인덱스 이동 ->  현재 저장되어있는 데이터를 삭제
            let gem = gems[firstIndex]
            newList.updateValue((newList[gem] ?? 0) - 1, forKey: gem)
            if newList[gem] == 0 {
                newList.removeValue(forKey: gem)
            }
            firstIndex += 1
        } else {
            // 마지막인덱스 이동 -> 데이터를 추가
            lastIndex += 1
            if lastIndex >= gems.count {
                break
            }
            newList.updateValue((newList[gems[lastIndex]] ?? 0) + 1, forKey: gems[lastIndex])
        }
    }
    
    return [min[0]+1, min[1]+1]
}