[백준] 3273 - 두 수의 합 (자바/Java)

문제

n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 (ai, aj)쌍의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수열의 크기 n이 주어진다. 다음 줄에는 수열에 포함되는 수가 주어진다. 셋째 줄에는 x가 주어진다. (1 ≤ n ≤ 100000, 1 ≤ x ≤ 2000000)

출력

문제의 조건을 만족하는 쌍의 개수를 출력한다.

 

---

N의 크기만큼의 boolean 배열을 선언해주고, 입력받은 값을 true로 설정하였다.

그리고 i가 true이고, x-i가 true인 경우 cnt를 하나씩 증가하였다.

이때 배열 index out of bound가 계속해서 발생했는데, x의 범위가 1부터 2000000이고, 입력 숫자는 최대 1000000이기 때문에, x-i가 배열의 크기를 넘어가는 경우도 있고, x가 i보다 작을 경우 x-i가 0보다 작은 경우가 생기기 때문이었다.

이 경우를 조건에 반영하니 통과했다 ~

package BOJ0807;

import java.util.Scanner;

public class BOJ_3273_두수의합 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		boolean[] arr = new boolean[1000001];
		for (int i = 0; i < N; i++)
			arr[sc.nextInt()] = true;
		int x = sc.nextInt();
		int cnt = 0;
		for (int i = 1; i < 1000001; i++) {
			if (arr[i] == true && (x - i) <= 1000000 && (x - i) >= 0 && arr[x - i] == true) {
				cnt++;
			}
		}
		System.out.println(cnt / 2);

	}

}