[백준] S3 3273번 두 수의 합 (JAVA)

문제 출처 - Baekjoon Online Judge

문제는 여기

3273번: 두 수의 합

[문제] 

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)

[출력]

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

 

 

---

[풀이]

1. 두 수의 합이 주어지는 조건 합과 동일해야 한다.

2. 입력받은 수는 정렬이 되지 않고 입력이 되기 때문에 모든 배열을 탐색하면서 비교해야 한다는 문제가 발생한다.

3. 오름차순으로 입력받은 수들을 정렬해주고 투 포인터를 이용해 비교해준다.

4. 오름차순 정렬이 되어있기 때문에 조건에 맞춰 한쪽씩만 비교대상을 바꿔주면 된다.

5. 조건합과 같을 때, 카운트를 증가시켜주고 마지막에 카운트를 출력해준다.

[접근]

1. 입력받은 수들을 오름차순으로 정렬해준다.

2. 정렬이 된 수들을 투 포인터를 사용해 처리해준다.

3. 합이 조건 합보다 작다면 왼쪽 포인터를 증가시켜 준다.

4. 합이 조건 합보다 크다면 오른쪽 포인터를 감소시켜 준다.

5. 합이 조건 합과 같다면 카운터를 증가시켜준다.

6. 모든 탐색이 끝나면 카운터를 출력해준다.

[코드]

package BOJ_silver;

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

public class Main_S3_3273 {
	static int n;
	static int arr[]; // 수열을 담을 배열
	static int sum; // 조건 합
	static int count; // 조건 합이 나오는 횟수

	public static void main(String[] args) throws Exception {
		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());
		}
		
		// 조건 합 입력받기
		sum = Integer.parseInt(br.readLine());
		
		// 입력받은 수들을 정렬하기
		Arrays.sort(arr);
		
		// 왼쪽 포인터는 0, 오른쪽 포인터는 n - 1
		int left = 0;
		int right = n - 1;
		
		// 왼쪽포인터가 오른쪽포인터보다 작을 때 
		while(left < right) {
			// 합이 조건보다 작다면
			if (arr[left] + arr[right] < sum) {
				left++; // 왼쪽 증가
			}
			// 합이 조건보다 크다면
			else if (arr[left] + arr[right] > sum) {
				right--; // 오른쪽 감소
			}
			// 합이 조건과 같다면
			else if (arr[left] + arr[right] == sum) {
				count++; // 카운트 증가
				left++; // 왼쪽 증가
				right--; // 오른쪽 감소
			}
		}
		
		System.out.println(count);
	}
}