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

프로그래머스

 

문제

 

모든 보석을 쇼핑하는 최단 부분수열을 구하는 문제이다.

---

풀이

해당 문제는 부분수열 문제와 비슷하기 때문에 투포인터를 이용하여 해결하였다.

기본적인 해결 과정은 다음과 같다.

1.  보석의 종류를 Set을 이용하여 중복되지 않게 저장한다.
2.  보석의 이름과 개수를 담을 map을 선언한다.
3.  반복문을 실행한다.
   
   1. 저장된 map의 크기와 모든 보석의 종류의 크기가 같다면 가장 왼쪽에 저장된 보석을 한개 제거한다. 이 때 보석의 개수가 0이라면 보석자체를 map에서 제거한다.
   2. map에 저장된 보석종류와 전체 보석종류의 개수가 일치하지 않고 커서가 오른쪽 끝에 도달하면 반복문을 탈출한다.
   3. 1, 2번 모두 아니라면 right커서가 가르키는 보석을 map에 추가시킨다.
   4. 1, 2, 3 번 이후 map의 크기와 전체보석 종류의 크기가 동일하다면 res값을 갱신한다.

다음을 코드로 구현하면 아래와 같아진다.

 

val sortOfGems = mutableSetOf<String>()
gems.forEach { sortOfGems.add(it) }

val map = mutableMapOf<String, Int>()

먼저 sortOfGems를 이용해 중복되지 않게 모든 보석종류를 저장하고, 현재 구매한 보석을 담을 map을 선언하였다.

 

반복문 내부는 아래와 같다.

if (map.size == sortOfGems.size) {
    map.put(gems[left], map[gems[left]]!! - 1)
    if (map[gems[left]] == 0) {
        map.remove(gems[left])
    }
    left++

만약 현재 구매한 보석의 종류와 모든 보석의 종류가 일치하다면 가장 먼저 구매한 보석을 제거한다.

이 때 가장 먼저 구매한 보석이 1개였다면 해당 보석을 map에서 제거한다.

이후 left커서를 증가시킨다.

 

else if (right == gems.size) break

만약 right커서가 마지막에 도달했다면 반복문을 탈출한다.

 

else {

    map.put(gems[right], map.getOrDefault(gems[right], 0) + 1)
    right++
}

모두 아니라면 right커서에 있는 보석을 현재 구매한 보석에 추가시켜준다.

 

if (map.size == sortOfGems.size) {
    if (res > right - left) {
        res = right - left
        start = left + 1
        end = right
    }
}

구매한 보석의 종류와 모든 보석의 종류가 일치하다면 res값을 갱신시켜준다.

 

---

코드

class Solution {
    fun solution(gems: Array<String>): IntArray {
        var answer = intArrayOf()
        
        var left = 0
        var right = 0
        var start = 0
        var end = 0
        var res = Int.MAX_VALUE
        
        val sortOfGems = mutableSetOf<String>()
        gems.forEach { sortOfGems.add(it) }
        
        val map = mutableMapOf<String, Int>()
        
        while (true) {
            if (map.size == sortOfGems.size) {
                map.put(gems[left], map[gems[left]]!! - 1)
                if (map[gems[left]] == 0) {
                    map.remove(gems[left])
                }
                left++
            } else if (right == gems.size) break
            else {
            
                map.put(gems[right], map.getOrDefault(gems[right], 0) + 1)
                right++
            }

            if (map.size == sortOfGems.size) {
                if (res > right - left) {
                    res = right - left
                    start = left + 1
                    end = right
                }
            }
        }
        return intArrayOf(start, end)
    }
}