[프로그래머스/Lv.3 (Swift)] 보석 쇼핑

2020 카카오 인턴십 > 보석 쇼핑

 

해당 문제는 슬라이드 윈도우, 투포인터를 이용해 해결할 수 있는 문제입니다.

 

1. 모든 종류의 보석을 하나 이상 포함하는 가장 짧은 구간만 구매하고자 합니다.
2. 모든 보석 종류를 하나 이상 포함하는 가장 짧은 연속 구간을 찾습니다. (제 글에서는 [Start, End]로 언급합니다.)

 

 

우선 문제를 마주했을 때, 전체 보석 종류가 주어지지 않기 때문에, 이를 탐색하는 과정에서 알아야 함을 알 수 있습니다. 저의 경우, 배열로 주어지는 gem을 Set로 만들어서 중복 값을 없애, 전체 존재하는 보석 종류를 미리 파악한 뒤 문제를 시작했습니다.

 

또한 [gem의 이름: 발견된 개수] 형태의 딕셔너를 활용해, 해당 탐색동안 보석이 얼만큼 존재하는지를 누적하면서 전개했습니다.

 

---

 

❎ 접근 방식 1: DFS

처음에는 해당 문제를 보고 DFS로 해결하고자 했습니다. 

시작값의 포인터를 하나씩 증가시키며, 보석의 개수를 모두 충족하면 가지치기를 하는 식으로 문제를 풀고자 했습니다. 그러나 DFS로 해결하기 위해서는 시작값을 전체 배열(N) 길이만큼 반복해 넣어주어야 하고, 해당 시작값으로부터 (N-1)만큼 더 탐색해주어야 하기 때문에 최악의 경우에는 시간복잡도가 O(N^2)이 됩니다.

 

후술하겠지만 해당 해결 방식은 시간복잡도 뿐만 아니라, 최적의 해답을 도출하지 못한다는 문제도 있었습니다.

 

 

❎ 접근 방식 2: End 값을 먼저 찾은 뒤, Start 값을 거꾸로 찾아가기

두 번째 접근 방식은 배열의 요소를 한 개씩 탐색하며, 가장 처음 만족되는 End 값을 찾은 뒤, 해당 End 값을 찾은 뒤로부터 -1를 반복하며 Start 값을 찾아가는 방식입니다. DFS로 접근했을 때보다 시간 복잡도는 줄어들지만 (O(N)), 일부 테스트 케이스에서 오답을 도출했습니다.

 

위 두 가지의 접근 방식에서 제가 간과했던 부분은, End의 값으로 가장 먼저 충족한 것이 항상 짧은 구간을 보장하는 것은 아니라는 점입니다. 위와 같이 풀었을 경우, 가장 처음 만족되는 구간을 발견할 수는 있지만, 이것이 가장 짧은 구간임은 보장되지 않습니다. (그 이후에서도 이보다 더 짧은 구간이 발견될 수도 있기 때문입니다.)

 

 

✅ 접근 방식 3: 슬라이딩 윈도우 활용하기

 

해당 탐색에서 관건이 되는 포인트는 두 가지입니다.

 

1. 구간이 모든 보석들을 한 개 이상 포함하는가?
2. 구간의 길이가 최소인가?

 

 

그래서 left, right 두 개의 포인터를 준비하고 left 포인터는 최소를 찾기 위해 (2번 조건), right 포인터는 모든 보석들을 한 개 이상 포함하기 위해 (1번 조건) 움직인다고 생각한 뒤 코드를 작성해 볼 수 있습니다.

 

 

조건문을 도식화하면 아래와 같습니다.

 

 

해당 조건을 반복하는 while문은 leftPointer <= rightPointer임을 만족하고, rightPointer < gems.count일 때만 돌아간다고 작성하면 됩니다.

 

 

---

느낀 점

경험이 많았다면, 연속된 배열에서의 최적의 구간을 찾는다는 조건을 보자마자 슬라이딩 윈도우 방식을 떠올려야 했을 것입니다. 아직 알고리즘에 부족함이 많다는 것을 깨닫고 더 열심히 공부해야겠다는 다짐을 했습니다.

 

제가 풀이한 방법은 아래와 같습니다.

 

import Foundation

func solution(_ gems:[String]) -> [Int] {
    
    let gemsSet = Set(gems)
    var gemsDict: [String: Int] = [:]
    
    var bestSection = (0, gems.count)
    var leftPointer = 0
    var rightPointer = 0
    
    while leftPointer <= rightPointer {
        // 만약에 gemsDict의 개수가 아직 보석 종류의 개수와 같지 않다면
        // rightPointer를 더 탐색해야 함
        if gemsSet.count != gemsDict.count {
            if rightPointer == gems.count { break }
            gemsDict[gems[rightPointer], default: 0] += 1
            rightPointer += 1
        } else {
            if rightPointer - leftPointer < bestSection.1 - bestSection.0 {
                bestSection.0 = leftPointer
                bestSection.1 = rightPointer
            }
            
            gemsDict[gems[leftPointer]]? -= 1
            // 만약 개수가 0이라면
            if gemsDict[gems[leftPointer]] == 0 {
                gemsDict[gems[leftPointer]] = nil
            }
            
            // 보석이 다 발견됐으므로 left를 오른쪽으로 밀음
            leftPointer += 1
        }
    }
        
    return [bestSection.0 + 1, bestSection.1]
}

 

 

실행 결과는 아래와 같습니다.