프로그래머스[programmers] - 보석쇼핑(Kotlin)[LV3]

문제

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

프로그래머스

 

문제 풀이

초기에는 N*N으로 탐색을 해서 요구사항에 맞는 짧은 구간, 길이가 같으면 시작 구간이 더 작은 구간을 함수를 통해서 반환했다.

정확성 테스트는 쉽게 통과했지만, 효율성 테스트에서 시간초과를 만날 수 있었다.

어쩐지 LV3 치고 문제가 너무 쉬웠는데, 아마 배열을 탐색하는 과정에서 N*N 알고리즘을 사용해서 그런 것 같다.

1차원이고, 완전 탐색을 피하기 위한 알고리즘으로 투포인터 알고리즘이 있다는 것을 저번에 공부했고,

투 포인터를 적용해보기로 했다.

 

아래 링크는 내가 정리한 투 포인터 알고리즘이다!!

https://jja2han.tistory.com/284

투 포인터 알고리즘(Two Pointer)

요약을 하자면 N^2의 시간을 N으로 줄일 수 있다.

아마 문제에서도 배열을 탐색하는 데 걸리는 시간복잡도를 줄여야 통과할 것이라고 생각했다.

 

우선 입력받은 보석의 배열에서 HashSet을 통해서 중복된 것들을 제외한 유효한 보석들만을 담는다.

이제 이 HashSet은 투 포인터 알고리즘에서 사용될 기준 가방이라고 생각하면 된다.

 

투포인터는 기본적으로 start와 end를 움직이면서 목표하는 요구사항을 만족하면 start를 한 칸 증가시켜 탐색범위를 감소시킨다.

우리는 보석을 담다가, 만약 기준가방의 보석의 개수와 일치한다면 start를 증가시켜 탐색의 범위를 감소시킬 것이다.

 

 

파란색은 start, 빨간색은 end이고, 초기값은 0에서 시작한다.

가방에 보석을 담기 전에, 가방의 보석이 몇종류 들어있는지 기준가방과 비교를 한다.

만약 일치하지 않는다면 가방에 보석을 담고, end를 한 칸 증가시킨다.

이렇게 쭉쭉 진행할 경우 end가 6일 때, 싸파이어를 담게 되고, end가 7일 때, 가방 검사를 해서 모든 종류의 보석이 담긴 것이 확인이 된다.

이럴 경우 Start에 해당되는 보석을 가방에서 빼야 한다.

따라서 가방은 HashMap으로 <보석의 이름, 보석의 개수>로 구현을 해서 보석의 개수가 1개일 경우, map에서 보석의 이름을 제거한다

그리고 start를 한 칸 증가시킨다.

아래와 같이 가방의 보석 종류가 기준 가방과 일치할 때까지 start를 증가시킨다.

 

start가 2인 구간에서 가방의 보석의 종류는 기준가방과 일치하고,

그 이후 반복문 조건(start <=end) 내에서 start를 증가시켜도 가방의 보석 종류가 기준가방과 일치하는 구간은 존재하지 않는다.

따라서 start는 2, end는 7을 반환하게 된다.

하지만 문제에서 구간은 1부터 시작하기에 요구사항에 맞게 start를 +1 해주면 된다.

 

처음에는 가방에서 보석의 개수를 0으로 만들고 , map에서 key를 지우지 않고, compareGems에서  아래와 같은 코드를 통해서 검사를 했다.

bag.count{it.value>0} == gemsSet.size

이렇게 구현을 하니 value를 탐색하는 시간 때문에 효율성 테스트에 통과하지 못했고, map의 key를 삭제하고,

map의 size를 그대로 비교하니 통과를 했다.

이렇게 사소한 부분에서 효율성 테스트에 걸릴 수 있으므로 주의해서 작성하도록 하자!!

 

Lv3 특히 정확성과 효율성을 동시에 검사하는 문제는 정말 정말 어렵다.. ㅠ

전체 코드

import java.util.*

class Solution {
    var gemSet = HashSet<String>()
    fun solution(gems: Array<String>): IntArray {
        var answer = intArrayOf(0, 0)
        for (gem in gems) {
            gemSet.add(gem)
        }
        val p = searchGems(gems)
        answer[0] = p.first + 1
        answer[1] = p.second
        return answer
    }

    fun searchGems(gems: Array<String>): Pair<Int, Int> {

        var start = 0
        var end = 0
        var bag = hashMapOf<String, Int>()
        var result = Pair(0, 100000)
        while (start <= end) {
            if (compareGems(bag)) {
                result = compareLength(result, Pair(start, end))
                if (bag[gems[start]] == 1) {
                    bag.remove(gems[start])
                } else {
                    bag[gems[start]] = bag[gems[start]]!!.minus(1)
                }
                start++
                continue
            }
            if (end == gems.size)
                break
            if (end < gems.size) {
                if (bag.contains(gems[end])) {
                    bag[gems[end]] = bag[gems[end]]!!.plus(1)
                } else {
                    bag.put(gems[end], 1)
                }
                end++
            }
        }
        return result
    }

    fun compareGems(bag: HashMap<String, Int>): Boolean {
        if (bag.size == gemSet.size)
            return true
        return false
    }

    fun compareLength(old: Pair<Int, Int>, new: Pair<Int, Int>): Pair<Int, Int> {
        val oldDiff = old.second - old.first
        val newDiff = new.second - new.first
        if (oldDiff > newDiff) {
            return new
        } else if (oldDiff == newDiff && new.first < old.first) {
            return new
        }
        return old
    }
}