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

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

programmers.co.kr/learn/courses/30/lessons/67258

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

풀이

set, map, queue를 사용하여 풀었다.

 

사용한 이유는 다음과 같다.

1. set은 보석의 종류의 개수를 알아내기 위해 사용하였고,

2. map은 보석의 종류별 개수를 기록하기 위해 사용하였고,

3. queue에는 보석의 순서대로 저장한 후 보석의 개수가 2개 이상이 되면 빼주도록 하여 문제에 조건에 맞는 보석의 구간을 구하기 위해 사용하였다.

하나씩 살펴보쟝.

 

1. set을 사용해 보석 종류의 개수를 알아낸다. 

반복문을 사용하여 hashset에 보석 정보를 입력하여 보석이 중복 없이 저장되도록 하였다.

이러면 반복문이 끝난 후 set의 크기가 보석 종류의 개수가 된다.

 

2. map을 사용해 보석 종류별 개수를 기록한다.

마찬가지로 hashmap을 사용하여 중복된 key가 저장되지 못하게 하였다.

또한 getOrDefault를 사용하여 key가 입력된 값이 아니면 value를 0으로 취급하고 그 값에 1을 더한 값이 저장되도록 하였다.

 

3. queue를 사용하여 조건에 맞는 보석의 구간을 구한다.

q에도 보석을 순서대로 넣어준다. 

그리고 q의 첫 번째 보석의 정보를 map에서 확인하여 1보다 크다면 q안에 해당 보석이 중복으로 들어왔다는 말이다. q에서 제거하고 map에서도 해당 보석의 value를 1 감소시킨다. 

map의 크기와 set의 크기가 같은지 확인한다. 같다면 모든 보석이 q에 한번 이상씩 포함되었다는 말이다.

현재 모든 보석이 포함된 길이(len)보다 q의 크기가 더 작은지 확인한다. 이 문제에서는 가장 짧은 구간을 구해야 한다.

더 작다면 q의 크기를 len으로 지정해주고, 시작 지점을 재설정 해준다. 

더 작지 않다면 위의 연산을 다시 반복한다.

 

코드

import java.util.*;
 
class Solution {
    
    Set<String> set = new HashSet<>(); //보석의 종류를 기록
    Map<String, Integer> map = new HashMap<>(); //보석의 종류별 개수를 기록
    
    public int[] solution(String[] gems) {
        for(int i = 0; i < gems.length; i++) {
            set.add(gems[i]);
        }
        
        int start = 0;
        int tempStart = 0;
        int len = gems.length;
        Queue<String> q = new LinkedList<>();
        for(int i = 0; i < gems.length; i++) {
            map.put(gems[i], map.getOrDefault(gems[i], 0) + 1);
            
            q.add(gems[i]);
            while(true) {
                String gem = q.peek();
                if(map.get(gem) > 1) {
                    map.put(gem, map.get(gem) - 1);
                    q.poll();
                    tempStart++;
                } else break;
            }
            
            if(map.size() == set.size()) {
                if(len > q.size()) {
                    len = q.size();
                    start = tempStart;
                }
            }
        }
        return new int[] {start + 1, start + len};
    }
}