[2020 카카오 인턴십]보석 쇼핑

📍 문제 설명

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

프로그래머스

 

💡 접근

투 포인터를 이용하여 풀 수 있는 문제

보석을 살 수 있는 구간일 때 범위를 계속 줄여가며 누적해야 한다.

 

👩‍💻 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public int[] solution(String[] gems) {
        int[] answer = new int[2];

        HashSet<String> set = new HashSet<>();
        HashMap<String, Integer> map = new HashMap<>();
        //보석 중복제거하여 저장
        for(String gem : gems) set.add(gem);

        int distance = Integer.MAX_VALUE;
        int start = 0, end = 0, lt = 0, rt = 0;
        //map 사이즈가 set 사이즈와 같으면 모든 보석을 하나이상 포함하는 구간이다.
        while(true) {
            //보석 살 수 있는 구간이면 범위를 줄여보기
            if(map.size() == set.size()) {
                //보석 빼기
                map.put(gems[lt], map.get(gems[lt]) - 1);
                //보석이 0개 라면 제거
                if(map.get(gems[lt]) == 0) map.remove(gems[lt]);
                lt++;
            }
            else if(rt == gems.length) break;
            //보석 살 수 없는 구간이면 범위를 늘려보기
            else {
                map.put(gems[rt], map.getOrDefault(gems[rt], 0) + 1);
                rt++;
            }

            //처리 후 살 수 있는 구간이라면 최소 거리를 누적
            if(map.size() == set.size() && rt-lt < distance) {
                distance = rt-lt;
                start = lt+1;
                end = rt;
            }
        }

        answer[0] = start;
        answer[1] = end;
        System.out.println(Arrays.toString(answer));

        return answer;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Main main = new Main();

        //String[] gems = {"DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"};
        String[] gems = {"A", "A", "B"};
        main.solution(gems);
    }
}