투포인터

2020 카카오인턴십 코딩테스트 - 보석쇼핑 문제에서 사용

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

기본적인 컨셉

  1차원 배열에서 start, end 두 인덱스 포인터를 두고 이동 시켜가면서 조건에 맞는 구간을 탐색

  1차원 배열의 모든 구간을 완전 탐색한다면 O(N^2)의 시간복잡도를 가진다. 위의 문제에서도 주어진 입력 배열 길이가 최대 100,000 건이므로 이를 완전탐색을 통해서 처리한다면 시간초과가 날 수 밖에 없다.

  투포인터 알고리즘을 통해서 두 개의 포인터를 통해서 처리한다면 각 인덱스가 0 → length(정방향) 혹은 length → 0(역방향)으로 움직이는 케이스를 확인하면 되므로 O(N)의 시간 복잡도로 문제를 해결할 수 있다.

  처음에는 이중 for문을 돌리되, 여러 break 조건을 두고 잘 핸들링하면 시간초과 없이 풀이가 가능할수도 있겠다는 생각을 했으나 선택한 알고리즘의 시간복잡도를 계산해보고 풀이 방법을 선택하는게 최선인 듯 하다

문제에서 적용

참고해야하는 조건

• gems 배열의 크기는 1 이상 100,000 이하

  → (해당 조건을 보고 완전탐색으로 풀이할 생각은 버려야한다)

• 전체 gems를 포함하는 가장 짧은 구간 도출

  → 포함여부를 체크하기 위해서 Set, Map 등의 자료구조가 필요하지 않을까?

• 짧은 구간이 여러개인 경우, 시작 인덱스가 가장 작은 케이스를 답으로 출력

해당 문제에서 투포인터 알고리즘을 적용한 풀이 아이디어는 다음과 같다.

1) 일단 기본적으로 전체 gems를 포함하는 구간을 찾아야하므로 이를 만족할때까지 end 포인터를 증가

2) 현재의 start - end 포인터 사이 구간에서 전체 gems를 포함한다면 start 포인터 증가

→ 전체 gems 포함이라는 조건은 만족하고 있는 상태이기 때문에 가장 짧은 구간을 구하기 위해서 start포인터를 증가시킨다

3) start, end 포인터가 전체 인풋 length까지 도달할때까지 1, 2의 작업을 반복한다. 그리고 전체 gems를 만족하는 시점에 조건을 확인하고 정답을 갱신

코드

import java.util.*;

class Solution {
    public int[] solution(String[] gems) {
        int[] answer = new int[2];
        int answerLen = Integer.MAX_VALUE;
        answer[0] = Integer.MAX_VALUE;

        // 전체 gems 체크용
        HashSet<String> gemSet = new HashSet<>(Arrays.asList(gems));

        // 각 구간별 보석 수
        HashMap<String, Integer> gemMap = new HashMap<>();

        int strtIdx = 0;
        int endIdx = 0;

        while(endIdx <= gems.length && strtIdx < gems.length){

            if(gemMap.size() == gemSet.size()){
                // 모든 보석 선택완료 시, strt증가 (최소 보석 수를 구하기 위해)
                strtIdx++;

                // answer 구하기
                                // 동일한 길이의 구간의 경우, 시작 진열대 번호가 더 적은 것으로 출력
                if(endIdx - strtIdx + 1 < answerLen || (endIdx - strtIdx + 1 == answerLen && answer[0] > strtIdx)){
                    answerLen = endIdx - strtIdx + 1;
                    answer[0] = strtIdx;
                    answer[1] = endIdx;
                }

                int curVal = gemMap.get(gems[strtIdx-1]);
                if(curVal-1 > 0) {
                    gemMap.put(gems[strtIdx-1], curVal - 1);
                }else{
                    gemMap.remove(gems[strtIdx-1]);
                }
            }
            else{
                if( endIdx == gems.length){
                    strtIdx++;
                }else {
                    gemMap.put(gems[endIdx], gemMap.getOrDefault(gems[endIdx], 0) + 1);
                    endIdx++;
                }
            }
        }

        return answer;
    }
}