[프로그래머스] 보석 쇼핑 (Swift)

https://school.programmers.co.kr/learn/courses/30/lessons/67258?language=swift

프로그래머스

투포인터 완탐 문제

 

접근방법

 

투포인터 초기 위치는 0번째 보석이다.

현재 구간에 포함된 보석 종류와 등장 빈도수를 저장하는 map이라는 딕셔너리를 갖고 간다.

구간이 변경될때마다 map 딕셔너리도 갱신된다. 없는 보석은 값이 0이 아니라 딕셔너리에서 제거되어야 함. (nil을 대입하는거에 번번이 실패해서, removeValue(forKey:) 메서드를 썼다.

gems 범위를 투 포인터가 벗어나지 않는 선에서

현재 구간이 전체 종류 보석을 포함하고 있다면,

우선 해당 구간의 길이를 현재 최단구간 길이와 비교한 뒤 더 작을 경우 구간을 저장해 준다 (rs, re에)

그리고나서, 이제 더 좋은 해답을 찾아서, s 시작점을 오른쪽으로 한칸 이동하는데, 이는 map에서 s 점에 있었던 보석을 빼주고 (0이 됐다면 아예 제거해주고), s를 1 증가시키는 걸 말한다.

근데 현재 구간이 전체 종류 보석을 모두 포함하지 못한다면, 구간을 늘려야 된다는 의미이므로 시작점이 아니라 끝점을 이동해준다 (오른쪽으로).

끝점을 이동해줄때는 현재 반복문에 들어올 수 있는게 e가 gems의 마지막 원소일때까지여서, 만약에 e가 마지막원소에 있을 때 1을 더해주고, 그 보석을 참조하려고 하면 범위를 넘어가기 때문에, 이때 범위체크를 한번 더해준다.

그러면 한칸 이동시 범위 내에 있다면 e번째 보석을 포함시킬 것이고,

한칸 이동시 범위를 벗어나면 e만 범위를 벗어난 채로 반복문이 종료될 것임

 

오답노트

오답노트는 마지막에 설명한 e 범위 초과 문제였다.

역시 차분하게 디버깅해보는게..좋다

 

 

소스코드

import Foundation

func solution(_ gems:[String]) -> [Int] {
    
    var n = Set<String>(gems).count
    
    var rs = 0
    var re = gems.count-1
    
    var s = 0
    var e = 0
    var map:[String:Int] = [:] // 현재 구간의 보석 종류 : 빈도수
    map[gems[0], default:0] = 1
    
    while e < gems.count && s <= e {
        if map.keys.count == n {
            // 현재 구간에 모든 종류 있음
            // 이 구간 저장 (현재 rs, re에 반영)
            if re-rs > e-s {
                re = e
                rs = s
            }
            // 시작점 위치 옮김 (한칸 오른쪽)
            map[gems[s], default:0] -= 1
            if map[gems[s]] == 0 {
                map.removeValue(forKey:gems[s])
            }
            s += 1
        } else {
            // 현재 구간에 모든 종류 보석 없음 -> 끝점 한칸 옆으로 이동
            e += 1
            if e < gems.count {
                map[gems[e], default: 0] += 1
            }
        }
    }
        
    return [rs+1, re+1]
}