[알고리즘] 2020 카카오 인턴십 - 보석 쇼핑 (Two Pointers Algorithm)

1. 문제

이번 문제는 2020 카카오 인턴십에 출제된 보석 쇼핑이라는 문제이다.

 

2. 문제 풀이

 처음에 어떤 알고리즘과 자료구조를 사용해야할지 감을 못잡아서 제대로 접근을 하지 못했었다. 이번 문제는 하나의 1차원 배열에서 left, right를 0으로 두고 left와 right를 조작해서 원하는 값을 찾는 투포인터스 알고리즘(Two Pointers Algorithm)문제이다.

 

1. 우선 현재 map에 들어있는 보석의 종류가 gems에 들어있는 보석의 종류보다 작을 경우 right를 1씩 증가시켜주면서map에다가 넣는다.

 

2. map에 들어있는 보석의 종류가 gems에 들어있는 보석의 종류와 같을 경우 left를 하나 증가 시켜주고 map에 들어있는 보석의 개수가 0개이면 map에서 해당 key를 삭제한다.

 

3. 1,2를 반복하면서 map에 들어있는 보석의 개수와 gems에 들어있는 보석의 개수가 같고 left와 right의 거리가 현재 distance보다 짧을 경우 start와 end, distance를 갱신한다.

 

4. right가 n과 같다면 반복문을 탈출한다.

 

투포인터스 알고리즘에 대해서 어느정도 알고 있다면 쉽게 접근할 수 있는 문제였다.

import java.util.*;

class Solution {

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

        HashSet<String> set = new HashSet<>();
        set.addAll(Arrays.asList(gems));

        int n = gems.length;
        int distance = Integer.MAX_VALUE;
        
        //정답 저장
        int start = 0;
        int end = 0;
        
        //범위
        int left = 0;
        int right = 0;

        HashMap<String, Integer> map = new HashMap<>();

        while (true) {
            if(map.size() == set.size()){  //left 오른쪽 이동
                map.put(gems[left], map.getOrDefault(gems[left],0) - 1);

                if(map.get(gems[left]) == 0)
                    map.remove(gems[left]);

                left++;
            } else if(right == n){
                break;
            } else { //right 오른쪽 이동
                if(right<n) {
                    map.put(gems[right], map.getOrDefault(gems[right], 0) + 1);
                    right++;
                }
            }

            if(map.size() == set.size() && right-left<distance){
                distance = right-left;
                start = left+1;
                end = right;
            }
        }

        answer[0] = start;
        answer[1] = end;

        return answer;
    }
    
}

3. 관련 문제

대표적인 투포인터스 문제를 풀고 싶다면 아래 링크를 참고하면 된다.

www.acmicpc.net/problem/2003

2003번: 수들의 합 2