[백준] Gold IV. 합이 0

https://www.acmicpc.net/problem/3151

 

문제 알고리즘

• 투 포인터
• 이분 탐색 

 

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int n;
    static int [] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        arr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();

        long cnt = 0;
        for(int i = 0; i < n; i++){
            for(int j = i + 1; j < n; j++) {
                int sum = arr[i] + arr[j];
                int lo = lowerbound(j+1, n-1, -sum);
                int hi = upperbound(j+1, n-1, -sum);
                cnt += hi - lo;
            }
        }
        System.out.println(cnt);
    }

    public static int lowerbound(int lo, int hi, int target) {
        while(lo <= hi) {
            int mid = (lo + hi) / 2;
            if (arr[mid] < target) {
                lo = mid + 1;
            }
            else {
                hi = mid - 1;
            }
        }
        return lo;
    }

    public static int upperbound(int lo, int hi, int target) {
        while(lo <= hi) {
            int mid = (lo + hi) / 2;
            if (arr[mid] <= target) {
                lo = mid + 1;
            }
            else {
                hi = mid - 1;
            }
        }
        return lo;
    }
}

 

 

회고

 

처음 문제 접근할 때 이분탐색으로 풀어야겠다고 생각해서 이런식으로 구현했었다.

for(int i = 0; i < n; i++) {
    int lo = i + 1;
    int hi = n - 1;
}

 

맨 왼쪽 값을 고정 시켜놓고, 그 다음 값을 lo, 끝 값을 hi로 두고 이분탐색을 하는 방식인데 이렇게 설정했을 때 시작점과 끝 점을 이동 시켜주는 방법을 찾지 못해서 답을 참고했다.

 

Upperbound, Lowerbound를 사용하는 풀이

10
2 -5 2 3 -4 7 -4 0 1 -6

 

이렇게 예제가 주어질 때, 정렬을 하면

-6 -5 -4 -4 0 1 2 2 3 7

 

이렇게 될 것이다.

(-5,2) 두 명을 미리 선택을 하고 나머지 값을 찾으면 된다.

 

(-5,2)일 때 lowerbound를 찾아보면, lowerbound(3)보다 크거나 같은 첫번 째 인덱스를 리턴해준다.

그래서 3에 해당하는 인덱스인 8을 리턴한다.

 

반면에, upperbound는 upperbound(3)보다 큰 첫번 째 인덱스를 리턴해주기 때문에 값이 3이 아닌, 7을 가르키게 되고 인덱스 9를 리턴해준다.

 

두 인덱스의 차이를 구해주면 결국 개수를 찾을 수 있다.

 

문제에서 중복값이여도 다른 참가자로 계산하기 때문에, (-5,2,3), (-5,2,3) 이 두개를 별개의 결과로 계산해서 더해주면 된다.

 

 

시작값 세팅

int lo = lowerbound(j+1, n-1, -sum);
int hi = upperbound(j+1, n-1, -sum);

 

이중 for문을 돌면서, 이분 탐색의 시작점은 j+1이 되게 한다. (j가 되면 안되는 이유는 arr[j]값이 겹친다.)

 

이렇게 되면 시간 복잡도가 O(N^2) * O(logN)이 되어서 N이 10,000일때도 시간 제한인 4초 안에 충분히 끊어진다.

 

lowerbound, upperbound 개념을 이해하기에 되게 좋은 문제같다.

 

참고한 블로그)

https://howudong.tistory.com/253

[C++] 백준/BOJ - 3151 : 합이 0