패스트캠퍼스 챌린지 26일차

카테고리 없음

패스트캠퍼스 챌린지 26일차

JUN0126 2022. 2. 18. 22:24

두 포인터(Two Pointer)

- 화살표 두개의 의미를 부여해서 탐색 범위를 압축하는 방법

1. 1차원 배열 위에 2개의 포인터를 만드는 경우

-1) 2개의 포인터가 모두 왼쪽에서 시작해서 같은 방향으로 이동

- 오른쪽 포인터가 먼저 이동하고 왼쪽이 따라감

-2) 2개의 포인터가 양 끝에서 서로를 향해 이동

-1)↓↓ ↓ ↓ ↓ ↓

0	1	2	3	4	5	67	7	8	9
10	11	18	19	38	58	72	87	92	66

-2) → ←

→ ←

<키워드>

- 1차원 배열에서의 "연속 부분 수열" or "순서를 지키며 차례대로"

- 곱의 최소

부분 합 (백준 1806)

- 접근

• 가장 쉬운 방법 O(N^2)

1. 왼쪽 시작 L결정 => O(N)

2. 오른쪽 끝을 R을 L로부터 시작해서 이동 => O(N)

3. 총 시간 복잡도 => O(N^2)

• 투 포인터 방법으로 접근

1. 왼쪽 시작 L결정 => O(N)

2. 오른쪽 끝을 R을 이전의 R부터 시작해서 이동

3. L, R이 각자 최대 N번 이동하니깐 => 총 O(N)

구현

    static int n, S;
    static int[] a; 

	static void pro() {
        int R = 0, sum = 0, ans = n + 1;
        for (int L = 1; L <= n; L++) {
            // L - 1 을 구간에서 제외하기
            sum -= a[L - 1];
            
            // R 을 옮길 수 있을 때 까지 옮기기
            while (R + 1 <= n && sum < S)
                sum += a[++R];
            
            // [L ... R] 의 합, 즉 sum이 조건을 만족하면 정답 갱신하기
            if (sum >= S)
                ans = Math.min(ans, R - L + 1);
        }

        // ans 값을 보고 불가능 판단하기
        if (ans == n + 1)
            ans = 0;
        System.out.println(ans);
    }

두 용액 (투 포인터 접근)

1. 최소 + 최대 < 0

-> 최소 입장에서는 최선책을 만난 상태, 짝을 찾았으니 삭제한다 (더이상 고려하지 않음)

2. 최소 - 최대 > 0

-> 최대 입장에서는 최선책을 만난 상태, 짝을 찾았으니 삭제한다 (더이상 고려하지 않음)

3 . L = R => 서로 다른 두 용액을 고를 수 없는 상태이므로 종료!

총 시간 복잡도 O(NlogN)

구현

	static int N;
    static int[] A;

	static void pro() {
        // 최소, 최대 원소를 빠르게 찾기 위해서 정렬을 미리 해주자.
        Arrays.sort(A, 1, N + 1);

        int best_sum = Integer.MAX_VALUE;
        int v1 = 0, v2 = 0, L = 1, R = N;

        while (L < R){  // L == R 인 상황이면 용액이 한 개 뿐인 것이므로, L < R 일 때까지만 반복한다.
            if (best_sum > Math.abs(A[L] + A[R])) {
                best_sum = Math.abs(A[L] + A[R]);
                v1 = A[L];
                v2 = A[R];
            }
            if (A[L] + A[R] > 0) R--;
            else L++;
        }
        sb.append(v1).append(' ').append(v2);
        System.out.println(sb);
    }