https://school.programmers.co.kr/learn/courses/30/lessons/67258
보석들의 목록이 주어진다.
모든 종류의 보석들을 최소 한 개 이상 구매할 수 있는 최소 길이의 구간을 찾는 문제이다.
["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"]
위와 같이 목록이 주어진다면 DIA, RUBY, EMERALD, SAPPHIRE를 한 개씩 구매 가능한 최소 길이 구간인 [3, 7]을 반환해야 한다.
배열의 크기가 최대 100,000이므로 이상의 알고리즘은 시간 초과가 날 수 있다.
문제를 많이 접해보지 않아 이하의 알고리즘을 생각해내기 힘들어 다른 풀이들을 참고하다가 투포인터 알고리즘이라는 것을 알게 되었다.
투포인터 알고리즘이란?
말그대로 start, end 두 개의 포인터를 통해 조건을 만족시키는지 확인하며 이동시키는 방법이다.
대표적인 문제는 자연수 배열에서 특정 합이 x인 구간을 찾는 문제이지만, 위 예제를 통해 투포인터 알고리즘을 학습해보자.
위와 같이 종류가 총 4가지인 보석 배열이 주어졌다.
두 포인터인 start, end 그리고 현재 보석 목록 배열을 준비한다.
현재 구매한 보석 종류가 0개 이므로, end 위치의 보석을 담고 우측으로 이동한다.
똑같이 현재 구매한 보석 종류가 1개 이므로, end 위치의 보석을 담고 우측으로 이동한다. 이 방법을 반복한다.
현재 구매한 보석 종류가 2개 이므로, end 위치의 보석을 담고 우측으로 이동한다.
현재 구매한 보석 종류가 3개 이므로, end 위치의 보석을 담고 우측으로 이동한다.
현재 모든 보석 종류를 구매했으므로, (start, end - 1) 위치를 저장한다.
+) 문제에서는 0위치를 1로 여기므로 실제 코드에선 (start + 1, end)를 저장함
단, 현재 최소 구간의 길이를 갱신하며 진행해야 한다. 현재까지는 최소 구간 정보가 없으므로, (1, 7)구간과 구간의 길이 7을 저장한다.
그리고 start위치의 보석을 한 개 제거하고 start를 우측으로 이동한다.
현재 상태에서도 모든 보석 종류를 구매한 상태이므로, 구간 정보를 갱신하고 start 위치의 보석을 제거 후 우측으로 이동한다.
이전 케이스와 동일하게 구간 정보를 갱신하고 start 보석을 제거 후 우측으로 이동한다.
현재 3종류의 보석을 구매한 상태이므로, end위치의 보석을 담고 이동시켜야 하나 end의 위치가 배열의 끝이므로 start를 end위치까지 한 칸씩 이동시킨다.
탐색이 끝났으므로, 현재까지의 최소 길이의 범위를 출력한다.
class Solution {
fun solution(gems: Array<String>): IntArray {
val set = gems.toSet()
val map = mutableMapOf<String, Int>()
var end = 0
var shortest = Int.MAX_VALUE
var shortestRange = Pair(0, 0)
for(start in gems.indices){
while(map.keys.size < set.size && end < gems.size){
if(map[gems[end]] == null) map[gems[end]] = 0
map[gems[end]] = map[gems[end]]!! + 1
end++
}
if(map.keys.size == set.size){
if(shortest > end - start){
shortest = end - start
shortestRange = Pair(start + 1, end)
}
}
map[gems[start]] = map[gems[start]]!! - 1
if(map[gems[start]] == 0) map.remove(gems[start])
}
return intArrayOf(shortestRange.first, shortestRange.second)
}
}보석의 구매 여부 및 개수 정보를 관리하기 위해 Map을 사용하였다. (보석, 개수)
구매한 보석 종류의 개수 (map의 key 개수)가 전체 보석 종류 개수(set 크기)와 동일한 경우에 start가 증가하도록 구현하였다.
그렇지 않고 구매한 보석 종류가 적다면, end가 증가하도록 하였다.
구매한 보석 종류의 개수를 key 개수로 지정하였으므로, start를 이동시킬 때 제거한 보석의 개수가 0이 되었다면, remove를 통해 제거하도록 하였다.
