[Algorithm] boj_1253 (투포인터)

문제

https://www.acmicpc.net/problem/1253

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

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

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

입력

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

출력

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

---

접근 방법

• 처음에는 문제의 조건을 착각해서 배열의 3번째 값부터 탐색하고, end 값을 i-1로 잡고 탐색했다.

  • 주어진 수들이 모두 자연수라면 이렇게 해야 하지만, 0 또는 음수도 나올 수 있다.
  • ex) N=4, [0,0,0,0] 일 경우 오답이 된다.

• 따라서, 배열의 첫번째 값부터 탐색하고 end를 배열의 마지막 값으로 초기화하고 탐색해야한다.

• 또한, 자기 자신은 포함하면 안되기때문에, start와 end 값이 현재 기준값이 되지 않도록 한다.
  
  

코드

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

public class boj_1253 {

    static int N;
    static int[] arr;
    static int answer;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new int[N];

		//input
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        //sort
        Arrays.sort(arr);

		//search
        for (int i = 0; i < arr.length; i++) {
            int target = arr[i];

            int start = 0;
            int end = arr.length - 1;

            while (start < end) {
                if (start == i) {
                    start++;
                    continue;
                }

                if (end == i) {
                    end--;
                    continue;
                }

                int curSum = arr[start] + arr[end];

                if (curSum == target) {
                    answer++;
                    break;
                } else if (curSum < target) {
                    start++;
                } else {
                    end--;
                }
            }
        }

        System.out.println(answer);
    }
}