[Programmers] 2020 카카오 인턴십 - 보석쇼핑 (Swift)

문제 : 

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

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

 

Step 1. 문제 이해하기

• gems 배열에는 보석들의 이름이 담겨있다.
• 모든 종류의 보석을 적어도 1개 이상 포함하면서 가장 짧은 연속하는 구간의 처음과 끝을 정수 배열로 출력
• 만약 가장 짧은 구간이 여러 개라면 시작 구간이 가장 작은 구간을 출력
• 배열의 크기는 최대 1 이상 100,000 이하

 

Step 2. 문제 풀이 생각하기

1. 연속하면서 가장 짧은 구간이라고 해서 투 포인터를 떠올렸습니다.
2. gems의 모든 원소를 확인하면서 set에 저장해야겠다고 생각했습니다.
3. 그리고 빈 set에 보석을 담고 빼고 하는 방식으로 구간을 찾으려고 했으나, 동일한 보석이 여러 번 나올 수 있고 여러 번 나온 보석을 하나씩 빼야 한다는 결론에 도달해서 빈 hash table로 만들어야겠다고 생각했습니다.
4. r(오른쪽 포인터)가 진행하면서 [현재 보석 개수(해시 테이블 크기)]와 [중복을 제거한 모든 보석 개수]를 비교해서 같지 않으면서 해시 테이블에 보석을 포함하고 있으면 빈 해시 테이블에 [보석명 : 현재 개수] 형태로 저장합니다. 이미 포함하고 있다면 현재 개수 + 1
5. (현재 보석 개수)와 (중복을 제거한 모든 보석 개수)가 같으면 해당 보석의 개수가 1이면 해당 보석 제거, 2개 이상이면 (현재 개수 - 1)
6. 가장 짧은 구간이라면 구간 길이를 갱신하고 [처음, 끝]을 저장
7. 4 ~ 6 반복

 

Step 3. 차근차근 구현하기

import Foundation

func solution(_ gems:[String]) -> [Int] {
    var ans = [Int]()
    let gemsLen = Set(gems).count // 중복을 제거한 모든 보석 개수
    var gemsHt = [String : Int]() // [보석명 : 개수] 저장하는 해시 테이블
    var l = 0
    var r = -1
    var minValue = 100000 // 가장 짧은 구간 길이
    
    while l < gems.count && r < gems.count {
        let gemCnt = gemsHt.count
        // 모든 보석을 아직 찾지 못했을 때, r위치에 있는 보석 개수 + 1
        if gemCnt != gemsLen {
            r += 1
            // 전체 배열 범위를 넘었을 때 끝내기
            if r == gems.count {
                break
            }
            if let tmp = gemsHt[gems[r]] {
                gemsHt[gems[r]]! = tmp + 1
            }
            // 보석이 없으면 추가하기
            else {
                gemsHt[gems[r]] = 1
            }
        }
        
        // 모든 보석을 찾았을 때, l위치에 있는 보석 개수 - 1
        else if gemCnt == gemsLen {
            // 가장 짧은 구간의 경우 구간길이를 갱신하고 구간의 [처음, 끝]을 ans에 저장
            if minValue > r - l {
                minValue = r - l
                ans = [l + 1, r + 1]
            }
            if let tmp = gemsHt[gems[l]] {
                // 현재 보석 개수가 1개라면 지우기
                if tmp == 1 {
                    gemsHt.removeValue(forKey: gems[l])
                }
                else {
                    gemsHt[gems[l]]! -= 1
                }
            }
            l += 1
        }
    }
    return ans
}

 

Step 4. 피드백

• 투 포인터를 사용해야 한다는 것은 알았지만, 실제 구현을 어떻게 해야 할지 생각하면서 시간을 오래 사용했습니다. 투 포인터 숙련도가 아직 미숙한 것 같습니다.