좋다

백준 1253번 좋다

N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다.

N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라.

수의 위치가 다르면 값이 같아도 다른 수이다.

입력

첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수)

출력

좋은 수의 개수를 첫 번째 줄에 출력한다.

예제 입력 1	예제 출력 1
10	8
1 2 3 4 5 6 7 8 9 10

풀이

입력 받은 수를 정렬한다.

1	2	3	4	5	6	7	8	9	10

포인터 i, j를 배열의 양 끝에 위치시키고 이동하며 탐색한다. 판별 대상이 되는 수를 K라고 하면

배열[i] + 배열[j] > K : j--;
배열[i] + 배열[j] < K : i++;
배열[i] + 배열[j] == K : i++; j--; or count++;

규칙에 따라 실행한다.

소스

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		final int N = Integer.parseInt(st.nextToken()); //배열 길이
		int input [] = new int[N];
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i < N; i++)
			input[i] = Integer.parseInt(st.nextToken());
		
		Arrays.sort(input);
		
		int count = 0;
		
		for(int i = 0; i < N; i++) {
			//인덱스는 양쪽 끝에 위치
			int index_left = 0;
			int index_right = N - 1;
			
			while(index_left < index_right) {
				if(input[index_left] + input[index_right] == input[i])
					if(i == index_left) { //다른 수 확인
						index_left++;
					}
					else if(i == index_right) { //다른 수 확인
						 index_right--;
					}
					else {
						count++;
						break;
					}
				else if(input[index_left] + input[index_right] > input[i])
					index_right--;
				else
					index_left++;
			}
		}
		
		System.out.print(count);
	}

}