[Swift 알고리즘] 프로그래머스(Lv.3) - 보석 쇼핑 / 2020 카카오 인턴십

안녕하세요. 개발 중인 정주입니다.

 

오늘은 "프로그래머스(Lv.3) - 보석 쇼핑" 문제를 풀었습니다.

 

---

 

Github

GitHub - jeongju9216/SwiftAlgorithm: 스위프트 알고리즘

 

문제 링크

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

 

---

풀이

이번 문제는 투 포인터 문제입니다.

 

투 포인터랑 두 개의 포인터를 움직이며 범위 체크 등을 하는 알고리즘입니다.

left, right를 움직이며 내부의 원소를 체크해야 하는 이번 문제에서 쓰기 적절합니다.

 

저는 다른 방식으로 접근해서 일부 테스트 케이스만 통과했습니다..

이번에도 1~2시간 고민하다 어쩔 수 없이 아이디어를 찾아보았는데요.

 

투 포인터라는 것을 본 후 왜 막혔는지, 왜 이 알고리즘을 써야 하는지 알게 되었습니다.

 

문제 풀이

먼저 Set을 이용해 보석의 종류가 몇 개인지 구합니다.

 

포인터로 사용할 left, right 변수를 선언하고 최소 거리를 구해야 하므로 minDist를 Int.max로 정의합니다.

start와 end를 담을 result도 함께 선언합니다.

 

gem이 나온 횟수를 담는 딕셔너리도 선언해줍니다.

여기서 넣는 횟수는 범위를 좁히는 데 사용됩니다.

 

left와 right는 gems의 범위 안에서 이동해야 하므로 gems.count 보다 작을 때까지 아래 로직을 반복합니다.

1. gemDict에 left 키가 존재하는지 확인합니다. 없다면 0으로 초기화 합니다.

2. gemDict의 count와 gem 개수가 동일한지 확인합니다.

2-1. 같다면 right - left로 거리를 구하고 최소 거리면 result를 갱신합니다.

개수가 같다면 left도 1만큼 감소 시켜야 합니다. 이는 보석을 사는 구간을 좁힌다는 의미입니다.

구간을 좁히는 이유는 최소 거리를 구해야 하기 때문입니다.

left가 음수가 되면 더이상 해당 보석을 디렉토리에서 삭제합니다.

2-2. 같지 않다면 right를 움직여줍니다. 이는 보석을 사는 구간을 넓힌다는 의미입니다.

 

위 로직을 반복하면 result에는 최소 거리의 범위가 존재합니다.

 

이렇게 투 포인터를 이용해 O(n)으로 답을 해결할 수 있습니다.

 

감사합니다!

---

전체 코드

import Foundation

func solution(_ gems:[String]) -> [Int] {   
    let gemCount: Int = Set(gems).count
    if gemCount == 1 {
        return [1, 1]
    }
    
    var gemDict: [String: Int] = [:]
    var left = 0, right = 0, minDist = Int.max
    var result: [Int] = [0, 0]
    
    while left < gems.count && right < gems.count {
        guard let _ = gemDict[gems[left]] else {
            gemDict[gems[left]] = 0
            continue
        }
        
        if gemDict.count == gemCount {
            if right - left < minDist {
                minDist = right - left
                result = [left+1, right+1]
            }

            gemDict[gems[left]]! -= 1
            if gemDict[gems[left]] == 0 {
                gemDict[gems[left]] = nil
            }
            left += 1
        } else {
            if let _ = gemDict[gems[right]] {
                gemDict[gems[right]]! += 1
                right += 1
            } else {
                gemDict[gems[right]] = 0
            }
        }
        
    }
    
    return result
}

---

아직은 초보 개발자입니다.

더 효율적인 코드 훈수 환영합니다!

공감과 댓글 부탁드립니다.