[프로그래머스] L3 보석 쇼핑 / 2020 카카오 인턴십 (Java)

카카오

[프로그래머스] L3 보석 쇼핑 / 2020 카카오 인턴십

[풀이]

투 포인터 문제로 HashMap을 사용해서 중복검사를 수행한다.

import java.util.*;
class Solution {
    public int[] solution(String[] gems) {
        int[] answer = new int[2];
        HashMap<String, Integer> map = new HashMap<String, Integer>();
        for(int i=0; i<gems.length; i++){
            if(!map.containsKey(gems[i]))
                map.put(gems[i], 1);
        }
        int size = map.size(); map.clear();
        int idx1 = 0; // 시작위치
        int idx2 = 0; // 끝위치
        int len = Integer.MAX_VALUE;
        boolean first = true;
        while(true){
            if(first){ // idx2에 위치하는 값 추가
                if(!map.containsKey(gems[idx2]))
                    map.put(gems[idx2], 1);
                else
                    map.put(gems[idx2], map.get(gems[idx2])+1);
            }
            if(size == map.size() && idx2-idx1 < len){
                answer[0] = idx1+1;
                answer[1] = idx2+1;
                len = idx2 - idx1;
            }
            
            // idx1 값이 중복되는 경우
            if(idx1!=idx2 && (gems[idx1]==gems[idx2] || map.get(gems[idx1]) > 1)){
                map.put(gems[idx1], map.get(gems[idx1])-1);
                idx1++;
                first = false;
                continue;
            }
            
            first = true;
            if(++idx2 == gems.length) // 종료조건
                break;
        }   
        return answer;
    }
}