투 포인터 알고리즘

시간이 없어 상당히 날림으로 썼으며, 생각나면 수정할 예정

 

 

 

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

 

투 포인터 알고리즘

배열에 시작점/끝점 포인터를 설정하고 포인터들을 이동시켜가면서 부분 배열을 비교하며 원하는 결과를 도출한다.

 

•  백준2003 - 수들의 합2 문제 (www.acmicpc.net/problem/2003)

N개의 수로 이루어진 수열 A에서 A[i]~A[j]의 합이 M이 되는 모든 경우의 수를 구하는 문제다.

즉 부분 수열이 M이 되는 모든 경우의 수를 구하는 것이다.

 

가장 쉽게 생각할 수 있는 것은 3중 for문을 사용하는 것이다. 

모든 수열의 크기에 대해 시작점을 바꿔가며 전부 선형으로 비교해보는 것이다.

// 초기 입력
int n = scanner.nextInt();
int m = scanner.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
	arr[i] = scanner.nextInt();
}

// 시작
// 3중 for문. 복잡도가 크다. 시간초과
int answer = 0;
for (int i = 1; i <= n; i++) { // 부분수열 크기
	for (int j = 0; j <= n - i; j++) { // 탐색 시작점
		int sum = 0;
		for (int k = j; k < j + i; k++) { // 탐색
			sum += arr[k];
			if (sum > m) break;
		}
		if (sum == m) answer += 1;
	}
}

그러나 이 방법은 효율성이 떨어진다.(시간초과) 수열의 크기는 최대 10000인데, 1~10000 모든 크기에 대해 모든 시작점을 확인하니까 이미 여기서만 O(n^2)이고, 실직적인 탐색작업까지 하면 그 이상이다. 

 

그래서 이 경우 투 포인터 알고리즘으로 해결한다.

// 투 포인터
int start=0;
int end=0;
int sum=0;
answer=0;
while(true){
    if(sum>=m){ // 범위를 좁히는 행위므로, 기존 start 인덱스의 값을 sum에서 빼야한다.
        sum-=arr[start];
        start++;
    }else if(end==n){
        break;
    }else{ // 범위를 넓히는 행위므로, 현재 위치의 값을 더한 뒤 이동한다.
        sum+=arr[end];
        end++;
    }

    if(sum==m){
        answer++;
    }
}

시작과 끝점을 각각 start, end라고 하고 초기값을 0으로 준다. 그리고 그 사이에 있는 값의 합은 sum이다.

초기값이 0, 0이면 그 사이에 아무것도 없는 것이다. (0, 1이 되어야 비로소 인덱스 0에 있는 값을 더한다고 생각하면 된다.)

 

목표값 m이 나올 때 까지 end를 이동시키며 값을 더한다. 

값을 더해나가다가 목표값 m을 넘어가거나 m이 된 경우엔 더 이상 범위를 확장시킬 필요가 없다.

이 경우 범위를 좁혀가며 새로운 경우의 수가 나오는지 확인해본다. 범위를 좁힐 땐 출발점을 올리면 된다. 

출발점을 올려서 가능한 경우의 수를 모두 확인해보고, 더이상 없다면 다시 end를 이동시켜 범위를 확장시켜나간다.

 

그리고 매 과정을 반복할 때 마다 sum이 목표값 m과 같아지면 count를 해줘야한다 (answer+1)

 

 

• 2. 보석 쇼핑

수들의 합2와 같은 방식으로 풀 수 있는데, 다른점은 배열에 정수가 아닌 문자가 온다는 것이다.

이 경우 map에다가 보석의 값을 다 넣어서 중복없이 보석 종류의 수만 구한다. -> 이 수가 곧 우리의 목표값이다.

 

여기선 배열이 정수가 아닌데 무엇과 비교를 하느냐? map의 value와 비교한다.

 

종류의 수를 구한뒤 맵을 초기화하고, 본격적으로 알고리즘을 수행한다.

 

마찬가지로 시작점과 끝점을 0으로 초기화해서 배열을 돌기 시작한다.

배열의 값을 직접 비교하지않고, 마주치는 배열의 값을 map에 put해서 기존의 value+1을 해주면서 현재 보석의 수를 카운트한다.

 

첫번째 문제에선 start를 움직이면 sum에서 값을 빼주었는데, 여기선 start를 움직이면 해당 보석의 개수를 1개 빼준다. (map에서 해당 키의 value를 -1)

이때, value가 0이되면 map에서 해당 key를 아예 삭제한다.

 

이렇게 하면 현재의 배열범위안에서 존재하는 보석만 map에 존재하게 된다.

즉 map의 size = 현재의 배열범위에 존재하는 보석

 

첫번째 문제에서와 똑같이, 우리가 목표로하는 목표값(전체 보석종류의 수)과  map.size()를 비교하며 두 포인터(시작점 끝점)을 이동시킨다.

 

import java.util.*;

/**
 * 투 포인터를 사용한다.
 * lo와 end를 이용하는데, 각 포인터를 이동시킬 때 마다 해당 위치의 보석이름을 map에서 빼거나 더해준다.
 * 그리고 매번 map에서 보석들의 개수를 확인한다.
 * minLeft와 minSize를 이용해 최저 시작점과 최저 길이를 메모리한다.
 */

class Solution {

    public int[] solution(String[] gems) {
        int[] answer = new int[2];
        Map<String, Integer> gemBucket = new HashMap<>();

        for (String gem : gems) {
            gemBucket.putIfAbsent(gem, 0);
        }

        int totalGems = gemBucket.size();
        gemBucket.clear();

        int lo = 0;
        int hi = 0;
        int minLeft = Integer.MAX_VALUE;
        int minSize = Integer.MAX_VALUE;

        while (true) {
            if (gemBucket.size() >= totalGems) {
                gemBucket.computeIfPresent(gems[lo++], (__, val) -> val - 1 == 0 ? null : val - 1);
            } else if (hi == gems.length) {
                break;
            } else {
                gemBucket.putIfAbsent(gems[hi], 0);
                gemBucket.computeIfPresent(gems[hi++], (__, val) -> val + 1);
            }

            // 모든 보석을 가지고 있다면 갱신
            if (gemBucket.size() == totalGems) {
                if ((hi - lo < minSize)
                        || (hi - lo == minSize && lo < minLeft)) {
                    minLeft = lo;
                    minSize = hi - lo;
                }
            }
        }

        answer[0] = minLeft + 1;
        answer[1] = minLeft + minSize;

        return answer;
    }
}

 

 

참고

https://m.blog.naver.com/kks227/22079516557