프로그래머스 - 보석 쇼핑

해당 알고리즘 자료는 제가 직접 푼 것도 있지만 다른 분들의 풀이과의 비교를 통해 더 나은 알고리즘을 공부하기 위해 정리한 것들입니다.

프로그래머스 - 보석 쇼핑

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

풀이 1. (초급) - HashMap과 TreeMap을 활용하여 간격을 조절

import java.util.*;

class Solution {
    public int[] solution(String[] gems) {
        int [] answer = new int [2];
	int max = 100000;
	HashSet <String> set = new HashSet<String>();
	for(String s : gems) set.add(s);
	HashMap <String, Integer> hmap = new HashMap<String, Integer>();
	TreeMap<Integer, String> tmap = new TreeMap<Integer, String>((a,b) -> a-b);
	for (int i = 0; i < gems.length; i++) {
		if(hmap.containsKey(gems[i])) tmap.remove(hmap.get(gems[i]));
			hmap.put(gems[i], i+1);
			tmap.put(i+1, gems[i]);
		if(set.size() == hmap.size()) {
			int l = tmap.firstKey(), r = tmap.lastKey();
			if(max > r - l) {
				max = r - l;
				answer[0] = l;
				answer[1] = r;
			}
		}
	}
        return answer;
    }
}

풀이 2. (중급) - HashMap으로 뒤를 점검하고, Queue를 통해 앞을 점검하여 간격을 조절한다.
// 정렬를 거치는 풀이 1에 비해 속도가 빠르다.

import java.util.*;

class Solution {
    public int[] solution(String[] gems) {
       HashSet <String> set = new HashSet<String>();
       HashMap <String, Integer> map = new HashMap<String, Integer>();
       LinkedList <String> qu = new LinkedList<String>();
       for(String s : gems) set.add(s);
	int l = 0, start = 0, length = Integer.MAX_VALUE;
	for (int i = 0; i < gems.length; i++) {
		map.put(gems[i], map.getOrDefault(gems[i], 0) + 1);
		qu.add(gems[i]);
		while(true) { // 앞부분을 정리
			String gem = qu.peek();
			if(map.get(gem) > 1) {
				map.put(gem, map.get(gem) - 1);
				qu.poll();
				start++;
			}else break;
		}
		if(map.size() == set.size() && length > qu.size()) { // length가 작아지면 갱신
			length = qu.size();
			l = start;
		}
	}
	return new int [] {l + 1, l + length};
    }
}