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

[문제]

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

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

[풀이]

투포인터 방식으로 배열을 탐색하는 방법이 핵심인 문제였습니다.

 

우선, 초기에 필요한 자료를 세팅하였습니다.

• Set<String> set으로 보석의 개수를 저장하였습니다.
• gems를 탐색하여 Map<String, Integer> pick에 각 보석의 개수를 저장하며 맨앞에서 구할 수 있는 보석세트를 저장해서 초기 start와 end를 저장하였습니다.

그다음, 투포인터 방식으로 left를 right를 갱신하며  gems배열의 끝까지 새로운 보석세트를 만들었습니다.

• left = start, right = end를 저장하고, right < gems.length 까지 탐색
• right++통해 오른쪽으로 한칸 확장하고, left부터 pick에서 보석개수를 구해와, 겹치는 보석이 있다면 ( 보석이 2개 이상이라면 ) 보석을 제거하며 left++를 진행하였습니다.
  여기서 핵심은, 각 보석이 최소 1개는 있어야지 보석세트가 완성되기 때문에, 만약 현재 left가 가르키는 보석이 pick에 1개만 존재한다면, left 갱신은 중단됩니다.

[코드]

import java.util.*;
class Solution {
    public static int N = 0; // 중복 제거된 보석의 총 개수
    public static int start = 0;
    public static int end = 0;
    public int[] solution(String[] gems) {
        int[] answer = new int[2];
        
        // 보석의 개수 구하기
        Set<String> set = new HashSet<String>();
        for(int i=0;i<gems.length;i++) {
            set.add(gems[i]);
        }
        N = set.size();
    
        Map<String, Integer> pick = new HashMap<String,Integer>();
        for(int i=start;i<gems.length;i++) {
            if(pick.get(gems[i]) == null) {
                pick.put(gems[i], 1);
            } else {
                int cnt = pick.get(gems[i]) + 1;
                pick.put(gems[i], pick.get(gems[i]) + 1);
            }
            if(pick.size() == N) {
                end = i;
                break;
            }
        }
        for(int i=start;i<end;i++) {
            if(pick.get(gems[i]) == 1) {
                start = i;
                break;
            } else {
                int cnt = pick.get(gems[i]) - 1;
                pick.put(gems[i], cnt);
            }
        }
        
        int left = start;
        int right = end + 1;
        
        while(right < gems.length) {
            int cnt = pick.get(gems[right]) + 1;
            pick.put(gems[right], cnt);
            
            // 오른쪽으로 확장
            for(int i=left;i<=right;i++) {
                cnt = pick.get(gems[i]);
                if(cnt == 1) {
                    left = i;
                    break;
                } else {
                    pick.put(gems[i], cnt - 1);
                }
            }
            if((right - left) < (end - start)) {
                start = left;
                end = right;
            }
            right++;
        }
        answer[0] = start + 1;
        answer[1] = end + 1;
        return answer;
    }
}