백준 3151 : 합이 0

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

3151번: 합이 0

[ 문제풀이 ]

예전에 풀어봤던 두용액문제랑 비슷한 유형인 것 같다.

3명의 코딩 실력 합이 0이 되어야 하기 때문에 2명의 코딩 실력을 선택하고 이들의 합을 0으로 만들 수 있는 코딩 실력을 가진 사람을 남은 범위에서 이분 탐색을 통해 찾아낸다.

다만, 정답이 될 수 있는 사람이 1명 이상일 수 있기 때문에 중복값의 범위를 탐색하기 위해 이분 탐색이 아닌 LowerBound와 UpperBound를 활용해준다.

LowerBound는 key 값보다 크거나 같은 첫 번째 인덱스를 찾아주고, UpperBound는 key 값보다 큰 첫 번째 인덱스를 찾아주기 때문에 가능한 사람의 수는 UpperBound 결괏값 - LowerBound 결괏값이 된다.

이를 활용해서 2명을 선택하는 모든 경우를 확인해주면 된다. 시간 복잡도가 O(N*N*logN)이라서 N이 최대 10000이면 TLE가 날 수도 있을 것 같았는데 운좋게 통과하였다.

정해는 투포인터를 이용해서 해결하는 방법이라고 한다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	static int N;
	static long ans;
	static int[] num;

	public static void main(String[] args) {
		try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
				BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))){
			N = Integer.parseInt(br.readLine().trim());
			StringTokenizer st = new StringTokenizer(br.readLine().trim());
			num = new int[N];
			for (int i = 0; i < N; ++i) {
				num[i] = Integer.parseInt(st.nextToken());
			}

			Arrays.sort(num);

			for (int i = 0; i < N - 2; ++i) {
				for (int j = i + 1; j < N - 1; ++j) {
					int key = -(num[i] + num[j]);
					int l = lowerBound(j + 1, N, key);

					if (l == N || num[l] != key) continue;

					int r = upperBound(j + 1, N, key);
					ans += r - l;
				}
			}

			bw.write(ans + "\n");
		} catch (Exception e) {
			e.printStackTrace();
		}
	}

	public static int lowerBound(int l, int r, int key) {
		int mid;
		while (l < r) {
			mid = (l + r) >> 1;
		if (num[mid] >= key) r = mid;
		else l = mid + 1;
		}
		return r;
	}

	public static int upperBound(int l, int r, int key) {
		int mid;
		while (l < r) {
			mid = (l + r) >> 1;
		if (num[mid] > key) r = mid;
		else l = mid + 1;
		}
		return r;
	}
}