백준 JAVA11 1253번 : 좋다

좋다

백준 1253번 상세보기

문제

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

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

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

힌트

3,4,5,6,7,8,9,10은 좋다.

Flow.

• 데이터를 오름차순 정렬
• 투 포인터 알고리즘을 사용하여 두 수의 합이 자신의 수와 같은 것을 출력한다.
• 다만, 포인터를 옮길때 자기 자신의 수를 포함하면 안된다.

Code.

import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();
		long number[] = new long[N];

		for (int i = 0; i < N; i++) {
			number[i] = sc.nextLong();
		}

		Arrays.sort(number);

		long cnt = 0;

		for (int i = 0; i < N; i++) {
			long goodNumber = number[i]; 
			int s = 0;
			int e = N - 1;
			while (s < e) {
				if (number[s] + number[e] == goodNumber) {
					if (s != i && e != i) { //자기 자신을 포함하지 않을때
						cnt++;
						break;
					} else if (s == i) { //자기 자신을 포함할때 
						s++;
					} else if (e == i) { //자기 자신을 포함할때
						e--;
					}
				} else if (number[s] + number[e] < goodNumber) {
					s++;
				} else {
					e--;
				}
			}
		}
		System.out.println(cnt);
	}
}