[Baekjoon 백준] 1253 좋다 - Java

문제) N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 "좋다(GOOD)"고 한다. N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라.

 

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

 

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

---

1. 변수 선언(N, M)

2. 주어진 수 배열에 저장, 정렬

3. 주어진 수 만큼 반복하면서 인덱스 배열의 합으로 좋은 수 찾기

 

public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine()); // 수의 개수 (|Ai| ≤ 1,000,000,000)
		long A[] = new long[N];
		StringTokenizer st = new StringTokenizer(br.readLine()); 
		for(int i=0; i<N; i++) {
			A[i] = Long.parseLong(st.nextToken());
		} 
		Arrays.sort(A);
		int count = 0; //좋은 수 개수
		for(int i=0; i<N; i++) { //주어진 수만큼
			long K = A[i]; //찾을 수
			int startIndex = 0;
			int endIndex = N-1;
			while(startIndex<endIndex) {
				long sum = A[startIndex] + A[endIndex];
				if(sum == K) { //두 포인터 합이 찾을 수랑 같을 때 => 좋은 수 대상
					if(startIndex != i && endIndex != i) { //자신 제외 일 때만 좋은 수
						count++;
						break;
					}
					else if(startIndex == i) { //시작 포인터가 i인 경우 ++
						startIndex++;
					}
					else if(endIndex == i) { //종료 포인터가 i인 경우 --
						endIndex--;
					}
				}
				else if(sum > K) { //찾을 수보다 합이 크면 종료 포인터 --
					endIndex--;
				}
				else {
					startIndex++; //찾을 수보다 합이 작으면 시작 포인터 ++
				}
			}
		}
		System.out.println(count);
	}

 

자기 자신은 제외한 수의 답을 찾으면서 투 포인터를 상황에 맞게 변경시켜준다.

어렵당.