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

문제

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

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

문제해결방법

이 문제를 풀기 위해 시작 인덱스와 끝 인덱스 두 개의 포인터를 사용하였다.

1. gems를 돌면서 Map에 존재하면 pass, 존재하지 않으면 해당 보석 이름을 Key로, Value를 0으로 해서 맵에 넣어준다
   -> 맵에 넣어줄때마다 카운트해서 보석의 종류의 개수를 알 수 있다.

2. 끝 인덱스를 배열의 0에서부터 증가시켜가며 보석의 종류별로 나온 횟수를 센다.
   (0에서 1이 되는 경우 카운트 하여 보석 종류 숫자가 될 때까지 탐색한다.)

3. 시작 인덱스를 0부터 끝 인덱스까지 하나씩 증가시키면서 보석이 나온 횟수를 -1 하는데 0이 되지 않는 경우만 증가시켜준다.

4. 끝 인덱스를 하나씩 뒤로 미뤄가면서 3번 과정을 반복한다.

5. 3번 과정을 할 때마다 길이를 최소 길이와 비교해가면서 더 작아질 때 시작 인덱스와 끝 인덱스를 기록한다.

코드

package Programmers;
 
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
 
public class Solution_보석쇼핑 {
    public static Map<String, Integer> map = new HashMap<>();
    
    public static int removeDupGems(int si, int ei, String[] gems) {
        for(int i=si; i<ei; i++) {
            if(map.get(gems[i])==1) break;
            map.put(gems[i], map.get(gems[i])-1);
            si++;
        }
        return si;
    }
 
    public static int[] solution(String[] gems) {
        int count = 0;
        for(int i=0; i<gems.length; i++) {
            if(!map.containsKey(gems[i])) {
                map.put(gems[i], 0);
                count++;
            }
        }
        int si = 0, ei = 0;
        int curCount = 0;
        while(curCount<count) {
            if(map.get(gems[ei])==0) curCount++;
            map.put(gems[ei], map.get(gems[ei])+1);
            ei++;
        }
        int min = ei-si;
        int minStartIndex = si, minEndIndex = ei-1;
        si = removeDupGems(si, ei, gems);
        if(min>ei-si) {
            min = ei-si;
            minStartIndex = si;
            minEndIndex = ei-1;
        }
        while(ei<gems.length) {
            map.put(gems[ei], map.get(gems[ei])+1);
            ei++;
            si = removeDupGems(si, ei, gems);
            if(min>ei-si) {
                min = ei-si;
                minStartIndex = si;
                minEndIndex = ei-1;
            }
        }
        int[] answer = {minStartIndex+1, minEndIndex+1};
        return answer;
    }
    
    public static void main(String[] args) {
        String[] gems = {"A", "B", "A", "A", "A", "C", "A", "B"};
        System.out.println(Arrays.toString(solution(gems)));
    }
}

코드에 대한 피드백이나 더 좋은 아이디어는 언제나 환영입니다.