백준 1253번 좋다(자바) - 투포인터 #

좋다 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

256 MB

16440

4036

2903

23.719%

문제

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

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

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

입력

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

출력

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

예제 입력 1 복사

10
1 2 3 4 5 6 7 8 9 10

예제 출력 1 복사

8

---

예외가 너무 많았던 문제..

처음에는 배열을 오름차순으로 정렬한 후 자신보다 작은 수에 대해서만 투포인터를 진행했다.

그런데 

-2 1 2 4 이런 경우 4 -2를 더하면 2가 나오므로 예외가 발생한다.

또한 0 0 3 3 3 의 경우에도 예외가 발생한다.

따라서 자신보다 작은 수에 대해서만이 아니라 전체 수에 대해 투포인터를 진행한다.

대신 자신을 포함하지 않도록 조건을 추가한다.

 

또한 처음에는 while(left < true) 처럼 코드를 작성했는데 이 경우 left와 right을 옮긴 후에 오류가 발생해서 틀린 값이 나왔다

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

public class Main {
    static int[] arr;
    static int cnt;
    static int n;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        Arrays.sort(arr);
        cnt = 0;
        for (int i = 0; i < n; i++) {
            twoPointer(i);
        }
        System.out.println(cnt);
    }
    static void twoPointer(int num) {
        int left = 0;
        int right = n-1;
        while (true) {
            if (left == num) left++;
            else if (right == num) right--;  //자신을 포함하지 않도록 조건 추가

            if (left >= right) return;
            if (arr[left] + arr[right] < arr[num]) left++;
            else if (arr[left] + arr[right] > arr[num]) right--;
            else {
                cnt++;
                return;
            }
        }
    }
}