[프로그래머스/자바] 보석 쇼핑 풀이 - 2020 카카오 인턴십

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

프로그래머스

 

 

2020 카카오 인턴십 Level 3 문제다.

 

 

1차원 배열이 주어지고 가장 짧은 구간을 찾는 문제기 때문에 바로 투포인트로 접근을 했다.

 

처음엔 HashMap이 아니라 배열을 통해 구간의 값들을 저장하고, for문을 통해 모든 종류의 보석이 담겨있는지 확인했기 때문에 시간 초과가 났다.

중복을 허용하기 않는 HashMap의 value값을 보석의 갯수로 저장하는게 포인트인 것 같다.

 

어떻게 하면 효율적으로 풀 수 있는지 단번에 파악하는 능력을 길러야겠다.

 

import java.util.HashSet;
import java.util.HashMap;

class Solution {
    public int[] solution(String[] gems) {
        HashSet<String> set = new HashSet<>();
        HashMap<String, Integer> map = new HashMap<>();
        
		for(String s : gems)
        	set.add(s);
		
		int start = 0, end = 0;
		int ans1 = 0, ans2 = 100000;
		
		if(map.size() == 1)
			return new int[] {1, 1};
		
		while(true) {
			if(set.size() == map.size()) {
				if(ans2 - ans1 > end - (start + 1)) {
					ans1 = start + 1;
					ans2 = end;
				}
				
				int i = map.get(gems[start]);
				if(i - 1 == 0)
					map.remove(gems[start]);
				else
					map.put(gems[start], i - 1);
				start++;
			} 
			else {
				if(end >= gems.length)
					break;
				map.put(gems[end], map.getOrDefault(gems[end], 0) + 1);
				end++;
			}
		}
		int[] answer = {ans1, ans2};
        return answer;
    }

}