프로그래머스 - 보석 쇼핑 (2020 카카오 인턴십)

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

코딩테스트 연습 - 보석 쇼핑

 

문제 정리 

1. 진열된 모든 종류의 보석을 적어도 1개 이상 포함하는 가장 짧은 연속된 구간을 구하세요. 

2. 만약 가장 짧은 연속된 구간이 여러개라면, 가장 왼쪽에 위치한 구간을 반환하세요. 

3. 진열된 모든 종류의 보석을 적어도 1개 이상 포함하는 구간은 무조건 1개 이상 존재합니다. 

 

접근 방법 

완전 탐색 

이 문제는 우선 정확도 평가와 효율성 평가가 존재한다. 효율성 평가가 존재한다면 보통 완전탐색을 이용하면 절대 풀 수 없는 문제를 의미한다고 볼 수 있다. 만약에 완전탐색을 이용하여 모든 구간을 탐색하여 가장 짧은 구간을 구한다면 보석의 개수가 최대 100,000개 이므로 최악의 경우 대략 100,000 * 100,000번 loop를 수행해야 한다.  즉, 완전 탐색으로 구현 해봤자 절대로 효율성 평가를 통과할 수 없다.

첫번째 방법 (실패) 

첫번째 생각해낸 방법은 정확도 평가에서 처참히 실패한 방법이다. 대충 로직을 설명하자면 

 

1. 모든 보석의 개수를 카운트하여 HashMap<보석 이름, 개수> gemsMap을 초기화 한다. 

2. 앞부터 보석을 하나씩 제외하며 만약 제외가 불가능(제외하면 조건이 충족되지 않을 경우)할 경우 루프를 종료한다.

3. 뒤부터 보석을 하나씩 제외하며 만약 제외가 불가능할 경우 루프를 종료한다.

4. 2,3번 로직을 거꾸로 반복한다. (뒤->앞, 앞->뒤 순) 

5. 2,3,4번 단계를 통해 얻어낸 두 가지의 해답의 길이를 비교한다.

  5-1. 만약 길이가 다를 경우 길이가 짧은 해답을 반환한다.

  5-2. 만약 같을 경우 더 앞에 위치한 구간의 해답을 반환한다. 

 

딱 보기엔 "어? 왜 안될까? 연속된 구간이니까 위의 로직을 적용한다면 모든 경우를 다 탐색하는 것과 같지 않을까?"라고 생각 할수도 있다. 하지만 위 로직에는 아주 치명적인 구멍이 존재한다.

 

만약에 "A", "B" ,"B", "C", "A", "B", "C", "A", "B", "C" 와 같은 테스트 케이스를 적용한다면 2,3번 로직을 진행한 경우 

맨 앞이 1번째라고 할 때 [8, 10]를 반환하고, 4번 로직을 진행한 경우 [1,4]를 반환한다. 그럼 결국 정답으로 길이가 짧은 [8,10]을 반환하게 된다. 하지만 위 테스트 케이스의 정답은 [3,5]이다.  애초에 위의 로직은 맨 앞, 맨 뒤에 위치한 해답만 찾아가는 로직인 것이다.  땡!

두번째 방법 (성공) 

두번째로 생각해낸 방법은 정확도 평가, 효율성 평가 모두 완벽하게 성공한 방법이다. 로직은 다음과 같다. 

 

1. left, right를 이용하여 구간을 지정한다. 

2. 만약에 조건을 만족하지 못하는 구간이면 뒤에 위치한 보석을 하나 더 선택한다. (right + 1)

3. 만약에 조건을 충족하는 구간이면 left에 위치한 보석을 제외시켜 조건을 충족할 수 있는지 확인한다.

  3-1. 만약 조건을 충족한다면 left에 위치한 보석을 제외시킨다. (left + 1) 

  3-2. 만약 조건을 충족하지 못한다면 뒤에 위차한 보석을 하나 더 선택한다. (right + 1) 

 

두번째로 생각해낸 로직은 left, right 두 변수를 이용하여 구간을 지정하여 만약 조건을 충족하는 구간이면 줄일 수 있는 대로 최대한 줄이고, 조건을 충족하지 못하는 경우면 보석을 하나 더 선택하여 조건을 충족하도록 늘려가는 로직이다. 위의 로직에 대해 좀 더 자세히 알고 싶다면 "투 포인터 알고리즘"에 대해서 공부하면 된다! 

 

구현 

import java.util.HashMap;

import java.util.Comparator;
import java.util.HashMap;
import java.util.PriorityQueue;

class Solution {
    public int[] solution(String[] gems) {
        int left = 0, right = 0, min = 654321;
        int kinds = getKindsByGems(gems);

        HashMap<String, Integer> gemsMap = new HashMap<>();
        PriorityQueue<int[]> areas = new PriorityQueue<>(Comparator.comparingInt(o -> o[0]));

        gemsMap.put(gems[0], 1);
        while(right < gems.length) {
            if(gemsMap.size() == kinds && min > (right - left)) {
                min = right - left;
                areas.clear();
                areas.add(new int[] {left + 1, right + 1});
            }

            if(gemsMap.size() == kinds && gemsMap.get(gems[left]) > 1) {
                gemsMap.put(gems[left], gemsMap.get(gems[left]) - 1);
                left += 1;
            }
            else {
                right += 1;
                if(right < gems.length) gemsMap.put(gems[right], gemsMap.getOrDefault(gems[right], 0) + 1);
            }
        }

        return areas.peek();
    }

    private Integer getKindsByGems(String[] gems) {
        HashMap<String, Integer> gemsMap = new HashMap<>();
        for (String gem : gems) {
            gemsMap.put(gem, gemsMap.getOrDefault(gem, 0) + 1);
        }

        return gemsMap.size();
    }
}

 

 

반성할 점 

어떻게 보면 정말 쉽게 풀 수 있는 문제였다. 첫번째 풀이 법을 생각한 후에 잘못된 것이라고 판단하여 빠르게 두번째 풀이 법을 떠올렸다. 하지만 생각보다 풀이가 오래 걸렸다.  이유는 예전부터 존재하는 나의 고질병인 "허둥지둥" 때문이였다. 로직을 확실하게 설계한 후에 코드를 작성해야 하는데 풀이 방법을 떠올렸다고 무작정 코드를 작성하다보니 구현에 생각보다 많은 시간이 소요되었다. 

 

다음부터는 확실하게 로직을 설계한 후에 코드로 옮기자! 제발!