LV3 [KAKAO] 보석 쇼핑

---

문제

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

프로그래머스

풀이

(자바로 풀이했다.)

 

투포인터를 활용해야하는 문제이다. 배열 크기가 10만이므로, for문 돌리면 시간초과가 나니까..

 

처음에는 난 양쪽 끝에서 투포인터를 사용하면 될 줄 알았다. 그러나 이럴 경우 중간에 가장 짧은 구간이 있을경우 캐치하지 못했다. 시간이 꽤나 걸려 카카오 공식 해설을 참조해서 풀었다.

 

 

우선 set과 같은 자료구조로 몇 종류의 보석이 존재하는지 체크한다.

 

이후에 r포인터를 늘리면서 map의 개수가 set의 개수와 같은지 (보석의 종류가 구간에 모두 있는지) 를 체크한다.

 

같은 경우에는 거리를 체크해서 최단 거리인지에 따라 갱신해준다. 그리고 l을 옮겨준다. l은 구간에 보석이 계속 존재할때까지 이동하면서, 정답을 체크한다. l은 이동하면서 map의 값을 계속 갱신해주어야 한다.

 

l이 이동하다가 더이상 map과 set의 크기가 같지 않다면, 다시 r을 이동시켜주면서 과정을 반복한다.

 

 

코드

import java.util.*;

class Solution {
    public int[] solution(String[] gems) {

        Map<String,Integer> map = new HashMap<>();
        Set<String> set = new HashSet<>(Arrays.asList(gems));

        int fptr = 0;
        int rptr = 0;
        int dis = 9999999;
        int start = 0;
        int end = 0;

        while (fptr < gems.length && rptr < gems.length) {
            if (map.containsKey(gems[rptr])) {
                Integer val = map.get(gems[rptr]) + 1;
                map.put(gems[rptr], val);

            } else {
                map.put(gems[rptr], 1);
            }
            rptr++;
            
            while (map.size() == set.size()) {
                if (dis > rptr - fptr) {
                    dis = rptr - fptr;
                    start = fptr;
                    end = rptr;
                }
                if (map.get(gems[fptr]) > 1) {
                    map.put(gems[fptr], map.get(gems[fptr]) - 1);
                } else {
                    map.remove(gems[fptr]);
                }
                fptr++;
            }
        }
        return new int[]{start+1, end};
    }

}

 

후기

 

투포인터까지 접근한건 좋은데, 아이디어가 틀려서 아쉬웠다. 구현위주의 문제를 풀다보니 이런쪽으로는 약하다는게 체감된다 ㅠ 그리고 LV3은 확실히 좀 어렵다.

 

자바로만 치는 코테가 있어서 자바로 풀어보고 있다. 확실히 파이썬보다는 까다로우나, 생각보다 어렵지는 않다.