[프로그래머스,Java] Level3: 보석 쇼핑

 

문제분석 

 

정확성 : Level3 

효율성 :(체감상) Level4 

 

문제 목표:  갑부 어피치는가 모든 보석의 종류를 구입할 수 있는 최단 구간을 구해주세요.

 

첫 정확성 풀이:

 

시작이 될수있는 번호가 예시로 주어진 문제에선 1번부터 8번까지니, 

 

 

이런 코드를 짯다.  for문 안에다  start_shopping으로  시작번호 i 에서부터 최단구간을 구하는것이다.

 

그렇게나온 여러개의 start_shopping의 결과물들을 

 

제일 구간이 짧고, 시작번호가 낮은 결과를 정렬해서 출력하는식으로 구현했다.

 

But....

 

기분 좋아졋다가  팍 식은 ..

 

시간복잡도를 한번 계산을 추측으로 해보니  O(T(종류)*log(n)*n) 정도 나온것같다.

 

 

여기서 최고 효율을 내려면  반복을 단 1번 O(n) 하게 짜야하는데 

 

데이터를 1번만 순회해서  어떻게 중간에  최단구간을 구할수있지..? 

아무리 생각해도 떠오르지않는다. 아니 애초에 가능은 한건가 싶었다.

 

<-- 놀랍게도 방법이 있더라 -->

 

누군가 올리신 기적같은 코딩

배운다는  자세로  자세하게 분석을 해보자.

 

1. 우선,  Set에다가  gems 배열을 넣어서  중복을제거해  보석의 종류 갯수를 구했다. (근데 이걸 1줄로..)

 

2.  맨 처음 구간의 길이를  터무니없게 높게 잡았다. 그 이유는  최소 구간을  업데이트하기 위함이다.

그리고  start 번호를 0으로 초기화

 

3. HashMap<String ,Integer> 로 선언했다.  여기서 Key는 보석  value는 보석의 갯수다.

 

4. 반복문을 시작한다.  반복기준은 역시 gems 배열

 

4-1.  map에다 보석을넣는다. 보석이 없으면 1개,  보석이 있으면, 저장된 보석에 +1개 저장한다. 

 

4-2.  start번째의 보석이 중복 이라면,  보석의 갯수를 줄이고  시작구간(start)을 1 증가한다.

 

4-3.  모든 보석을 탐색 했고,  최단 구간이면   최단 구간을 업데이트한다.

 

 

이 로직의 핵심은 바로  3번과 4-2 번 이다.

 

그냥 .. 아름다운 코딩이다.  짧고 효율적인 코드..

 

보통 for문을 작성하면  idx를 1개로 잡는데, 이 로직은  idx가 2개로 이루어져있다. (start와 end)

고정관념을 깨니 효율적인 코드가 나온것이다.

 

   

전체 코드

 

import java.util.*;
class Solution {
    public int[] solution(String[] gems) {
        int kind = new HashSet<>(Arrays.asList(gems)).size();
 
        int[] answer = new int[2];
        int length = Integer.MAX_VALUE, start = 0;
               
        Map<String, Integer> map = new HashMap<>();
        
        for (int end = 0; end < gems.length; end++) {
            map.put(gems[end], map.getOrDefault(gems[end], 0) + 1);
 
            while (map.get(gems[start]) > 1) {
                map.put(gems[start], map.get(gems[start]) - 1);
                start++;
            }
 
            if (map.size() == kind && length > (end - start)) {
                length = end - start;
                answer[0] = start + 1;
                answer[1] = end + 1;
            }
        }
 
        return answer;
    }
}