[백준] 1253 좋다 (투 포인터) - Java

 

1253번: 좋다

 

문제 상황

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

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

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

입력

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

출력

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

 

접근법

• 주어진 수들을 배열에 넣어 오름차순으로 정렬
• 배열의 첫번째 값부터 마지막 값까지
  • 투포인터를 배열의 양 끝 인덱스 left right 로 설정하고 투포인터를 이동하며 합이 같으면 count+1 하고 break
  • 단, 자기 자신은 좋은 수 만들기에 포함하지 못하기 때문에 left right 가 자신의 인덱스와 같을 경우 계속 투포인터를 이동함
  • 음수가 존재할 수 있기 때문에 투포인터는 항상 배열의 양 끝에서 시작해야함

 

문제 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        long[] arr = new long[N];

        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int count = 0;

        Arrays.sort(arr);

        for (int i = 0; i < N; i++) {

            int left = 0;
            int right = N - 1; // 음수값이 있으므로 전체 범위

            while (left < right) {
                long sum = arr[left] + arr[right];

                if (sum == arr[i]) {

                    if(left == i) left++;
                    else if(right == i) right--;
                    else{
                        count++;
                        break;
                    }

                } else if (sum < arr[i]) {
                    left++;
                } else {
                    right--;
                }
            }

        }

        System.out.println(count);
    }
}