[BOJ] 1253 좋다 - JAVA

1. 문제

1253번: 좋다

N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다.
N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라.
수의 위치가 다르면 값이 같아도 다른 수이다.

---

2. 풀이

1.  입력받은 배열을 정렬한다.

2.  배열 요소를 하나씩 찾는다. left = 0, right = N-1로 두고 탐색한다.

3.  sum = arr[left] + arr[right]이다. 

3-1.  sum > find 라면 더 작아져야하므로 right--한다.

3-2.  sum < find 라면 더 커져야하므로 left++한다.

3-3.  sum == find이지만 left == i 이거나 right == i 인 경우 해당 위치를 한칸씩 옮긴다.

3-4.  그밖의 경우는 답이다. 따라서 answer++한다.

4.  answer을 출력한다.

import java.io.*;
import java.util.*;
 
public class BOJ_1253_좋다 {
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      int N = Integer.parseInt(in.readLine());
      int[] arr = new int[N];
      StringTokenizer st = new StringTokenizer(in.readLine());
      for (int i = 0; i < N; i++) arr[i] = Integer.parseInt(st.nextToken());
      Arrays.sort(arr);
 
      int find, answer = 0;
      for (int i = 0; i < N; i++) {
         find = arr[i];
         int left = 0, right = N - 1, sum;
         while (left < right) {
            sum = arr[left] + arr[right];
            if (sum > find) right--;
            else if (sum < find) left++;
            else if (left == i) left++;
            else if (right == i) right--;
            else {
               answer++;
               break;
            }
         }
      }
 
      System.out.println(answer);
   }
}

---

3. 결과