프로그래머스 - 보석 쇼핑(Java)

투포인터 문제입니다.

투포인터는 O(N^2) 시간 복잡도를 가지는 이중 반복문을 단일 반복문으로 줄여주기 때문에 O(N)의 시간 복잡도를 가져 매우 빠른 연산이 가능합니다.

혹시 투포인터가 어떤건지 잘 모르시는 분은 https://ksb-dev.tistory.com/105에 정리 및 예제를 통한 설명이 있으니 꼭 읽어보시기 바랍니다.

 

이 문제의 경우 두 개의 포인터를 같은 위치에 두고 시작해야 합니다.

두 개의 포인터를 각각 LP(Low Pointer), HP(High Pointer)라 하겠습니다.

 

그림과 같이 있을 때, 보석의 종류는 {DIA, RUBY, EMERALD, SAPPHIRE} 입니다.

우선 HP를 모든 보석의 종류를 포함할 때 까지 움직여야 합니다.

그러면 위 그림과 같이 HP를 6번 움직여야 합니다.

HP와 LP의 거리가 6입니다.

HP가 모든 보석의 종류를 포함시켰으니 LP를 움직여 두 포인터 사이가 모든 보석을 포함하지 않게 만들어야 합니다.

그림과 같이 LP를 한 번만 움직이면 여전히 모든 보석을 포함하고 있습니다.

거리는 5입니다.

문제 조건에 의해 모든 보석을 포함하면서 거리가 최소인 LP와 HP를 구하는 것이기 때문에 정답을 갱신 합니다.

LP를 한 번 더 움직여 봅니다.

그래도 모든 보석을 포함하면서 거리가 4로 줄어들었습니다.

그러면 또 다시 정답을 갱신합니다.

위 그림과 같이 LP를 시점에서 부터 총 세 번 이동 시켜야 RUBY가 빠져 모든 보석을 포함하지 않게 합니다.

위와 같은 로직을 반복해서 HP가 배열 끝에 오고 LP가 HP 바로 이전(LP=HP-1)에 오게 만들면 끝납니다.

여기서 의문이 생길 수 있습니다.

"왜 LP를 HP이전 까지 옮겨야 하나요?"

이 의문은 또 다른 예시를 통해 설명 드리겠습니다.

이 예시는 테스트 케이스 6번과 7번에 관련되었습니다.

 

위와 같은 예시가 있습니다.

우선 HP가 모든 보석을 포함하도록 움직여야 합니다.

현재 HP와 LP 사이의 거리는 3 입니다.

그 다음 LP를 움직여 모든 원소를 포함하지 않도록 합니다.

다시 HP를 움직여 모든 원소를 포함하지 않게 합니다.

이제 보이시나요?

육안으로 봤을 때, 최소는 {EMERILD, RUBBY, DIA}순 이면서 그 거리는 2입니다.

근데, HP가 끝에 왔지만 아직 최소 거리는 3입니다.

이 예제 때문에 LP==HP-1을 만족할 때 까지 움직여야 합니다.

 

이제야 모든 배열을 포함하면서 최소인 거리가 되었습니다.

 

투포인터에 대한 설명이 끝났습니다.

그럼 이제 구현하면 되지 않을까요?

보석이 배열로 주어졌으니 SET에 넣어 어떤 보석 종류가 있는지 확인하면 될 것이고,

HP와 LP 사이에 있는 부분 배열들은 LIST에 담아서 처리하면 되겠다!!!

 

안됩니다.(ㅠㅠ)

 

SET을 통해 보석의 종류를 알아내는 것은 맞습니다.

하지만, LIST를 사용하면 안됩니다.

LIST의 요소를 삭제(remove) 및 조회(get) 할 때, O(N)의 시간 복잡도가 걸리기 때문에 이 문제의 경우 시간 초과가 발생합니다.

 

그러면 어쩌피 처음부터 순서대로 넣을 것이기 때문에 Queue를 사용하면 안될까요?

 

네, 안됩니다.

자바의 Queue는 LinkedList로 구현되어 있고, LinkedList 역시 조회(get)할 때 O(N)의 시간 복잡도가 걸립니다.

 

이것도 안된다 저것도 안된다라고 하시면 뭘 어떻게 처리해야 하나요?

get과 remove를 O(N)보다 적게 걸리는 자료구조가 있나요?

 

있습니다.

그것은 바로 MAP입니다.

 

MAP은 키 값으로 조회및 삭제를 할 수 있기 때문에 O(1)의 시간 복잡도로 처리할 수 있습니다.

또한, Map의 getOrDefault()를 사용하면 코드가 간결해 집니다.

 

[구현 코드]

import java.util.*;

class Solution {
    public static int[] solution(String[] gems) {
        Set<String> totalList = new HashSet<>(Arrays.asList(gems));
        int totalJemBumCnt = totalList.size();

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

        int hp = 0;
        int lp = 0;
        int hold = 0;

        // 구간의 최대 크기는 100,000
        int maxSection = 100_010;
        int ansL = maxSection;
        int ansH = maxSection;

        while (true) {
            hold = map.size();

            // 모든 보석을 포함할 때의 가장 짧은 구간을 구함
            if (hold == totalJemBumCnt) {
                int cs = hp - lp;

                if (cs == maxSection) {
                    if (lp < ansL) {
                        ansL = lp;
                        ansH = hp;
                    }
                } else if (cs < maxSection) {
                    maxSection = cs;
                    ansL = lp;
                    ansH = hp;
                }
            }

            if (hold < totalJemBumCnt) if (hp < gems.length) {
                map.put(gems[hp], map.getOrDefault(gems[hp], 0) + 1);
                hp++;
            }
            if (hp == gems.length && lp == hp - 1) break;
            if (hold == totalJemBumCnt || (hp == gems.length && lp < hp)) {
                if (map.getOrDefault(gems[lp], 0) > 1) {
                    map.put(gems[lp], map.get(gems[lp]) - 1);
                } else {
                    map.remove(gems[lp]);
                }
                lp++;
            }
        }

        // 부분 합으로 최소를 구할 수 없을 때
        // 즉, 처음부터 마지막까지의 보석을 모두 포함해야 정답일 때(테스트 케이스 4번)
        if (ansL == maxSection && ansH == maxSection) {
            ansL = 0;
            ansH = gems.length;
        }

        // 배열 0번부터 쓰기 때문에 +1을 해줌
        // ansH는 후위 연산자로 인해 마지막에 +1된 상태로 끝남
        return new int[]{ansL + 1, ansH};
    }
}