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

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

프로그래머스

 

2023.07.12 기준 Level 3

 

알고리즘 공부용으로 풀고 기록하는 글입니다!
참고만 해주시고 더 좋은 풀이법이 있다면 알려주세요!

 

아이디어

1. 모든 종류의 보석을 최소 1개 이상 다 사야합니다.
2. 1번을 만족하는 구간 중에서 가장 짧은 구간을 구해야 합니다.
3. 가장 짧은 구간이 여러 개라면 시작 진열대 번호가 작은 구간을 return 합니다.

우선 1번 요구 사항을 위해 보석 종류의 개수를 구해야 합니다.

주어진 보석 데이터는 배열이기 때문에 보석 종류의 개수는 직접 구해야 하는데 이건 Set을 사용하면 쉽게 구할 수 있습니다.

 

2번 요구 사항이 관건입니다.

일단 순차적으로 모든 종류의 보석을 최소 1개 이상 구하는 구간을 구하는 방법을 생각했습니다.

제일 간편한 방법으로 0번째 인덱스부터 시작해서 점점 범위를 늘려서 모든 종류의 보석을 다 살 수 있는 지점을 찾으면 됩니다.

이를 위해 범위의 시작 지점인 start와 마지막 지점인 end를 변수로 만들어 투 포인터로 범위를 핸들링합니다.

 

특정 구간 내에 속한 보석의 개수는 딕셔너리로 저장하면 효율적입니다.

 

이렇게까지 하면 모든 종류의 보석을 전부 살 수 있는 범위를 구할 수 있는데 이제 구간을 짧게 만들 차례입니다.

end를 증가시키면 구간을 늘릴 수 있고 start를 증가시키면 구간을 줄일 수 있습니다.

 

1번 요구사항을 만족하는 상황이라면 start를 1씩 늘리면서 구간을 줄여봅니다.

구간을 줄이다 보면 다시 1번을 불만족하는 상황이 발생하는데 이러면 다시 end를 증가시켜 구간을 늘려봅니다.

 

이 작업을 계속 반복하면서 요구 사항을 만족하면서 가장 짧은 구간을 구하면 됩니다.

 

예시

4종류의 보석(RUBY, DIA, EMERALD, SAPPHIRE)을 포함해야 합니다.

1	2	3	4	5	6	7
DIA	RUBY	RUBY	DIA	EMERALD	SAPPHIRE	DIA
start, end

end를 증가시켜서 4종류의 보석을 만족하는 구간을 찾습니다.

1	2	3	4	5	6	7
DIA	RUBY	RUBY	DIA	EMERALD	SAPPHIRE	DIA
start					end

start를 증가시켜 구간을 축소합니다.

1	2	3	4	5	6	7
DIA	RUBY	RUBY	DIA	EMERALD	SAPPHIRE	DIA
	start				end

위의 상황에서도 모든 요구사항을 만족하기 때문에 정답의 후보로 기록합니다.

1	2	3	4	5	6	7
DIA	RUBY	RUBY	DIA	EMERALD	SAPPHIRE	DIA
		start			end

위의 상황에서도 모든 요구사항을 만족하기 때문에 정답의 후보로 기록합니다.

 

1	2	3	4	5	6	7
DIA	RUBY	RUBY	DIA	EMERALD	SAPPHIRE	DIA
			start		end

이제 1번 요구사항을 만족시키지 못하기 때문에 end를 증가시킵니다.

이후 과정 생략.

 

 

풀이

fileprivate func solution(_ gems:[String]) -> [Int] {
    let gemKinds = Set(gems)
    var gemDict = [String: Int]() // 각 보석의 개수를 저장, key: 보석 이름, value: 보석 개수
    
    var start = 0
    var end = 0
    
    var result = [1, gems.count]
    
    // 구간(범위)의 길이
    var distance: Int {
        result[1] - result[0]
    }

    gemDict[gems[0]] = 1   // 첫번째 보석을 넣고 시작 (start와 end가 0부터 시작하기 때문)
    
    while end < gems.count && start <= end {
        if gemDict.keys.count == gemKinds.count {
            // 보석을 다 찾음 => 길이를 줄여야 함
            if end - start < distance {
                result = [start+1, end+1]
            }
            
            let gem = gems[start]
            gemDict[gem, default: 0] -= 1
            
            // 보석이 0개가 되면 딕셔너리에서 key 삭제
            if gemDict[gem] == 0 {
                gemDict.removeValue(forKey: gem)
            }
            
            start += 1
        } else {
            // 보석의 종류가 부족하기 때문에 범위를 늘려서 더 찾는다.
            end += 1
        }
    }

    return result
}

start와 end가 인덱스 0부터 시작하고 while문에서는 end += 1 을 실행하기 때문에 end = 0 일 때의 보석을 검사하지 않습니다.

따라서 while문 이전에 gemDict[gems[0]] = 1 을 실행하여 0번째 보석을 딕셔너리에 넣고 시작해야 합니다.

 

 

 

마무리

집합과 딕셔너리의 활용을 기반으로 투 포인터로 문제를 해결했습니다.

시간 복잡도를 낮추기 위해 계속 구간을 탐색하는 것이 아니라 포인터들을 1씩 증가 시키면서 증가한 만큼의 보석만 딕셔너리에 기록하는 방식입니다.