백준 1253 좋다

문제

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
힌트
3,4,5,6,7,8,9,10은 좋다.

---

풀이

public static void main(String[] args) throws IOException {
		
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer token = new StringTokenizer(bf.readLine());
        // 입력 받을 숫자의 개수 N
        int n = Integer.parseInt(token.nextToken());
        // 각 숫자를 저장할 배열
        long[] arr = new long[n];
        token = new StringTokenizer(bf.readLine());
        for (int i = 0; i < n; i++){
            arr[i] = Long.parseLong(token.nextToken());
        }
        // 배열을 오름차순 정렬
        Arrays.sort(arr);
		
        // 좋은 수의 개수를 누적할 변수
        int count = 0;
        
        for (int i = 0; i < n; i++){
            int start = 0;
            int end = n-1;
            long target = arr[i];
            while (start<end){
                long sum = arr[start] + arr[end];
                if (sum == target){
                    if (start != i && end != i){
                        count++;
                        break;
                    } else if (start == i) {
                        start++;
                    } else if (end == i) {
                        end--;
                    }
                }else if(sum < target){
                    start++;
                }else {
                    end--;
                }
            }
        }
        System.out.println(count);
        bf.close();
    }

리뷰

처음에는 문제를 잘 못이해를 해서 N의 범위를 0<N<=1,000,000,000이라고 생각했다.
그래서 end포인트를 n-1이 아니라 i-1로 설정해서 i=2일때부터 좋은수를 찾도록 설정했는데, 이것이 문제였다.
N의 범위가 절대값N<=1,000,000,000이므로 음수가 나올 수 있는데, 음수의 경우를 전혀 고려하지 않은 것이다.
위의 풀이는 음수가 있을 경우도 포함한 코드로, 포인터를 배열의 시작과 끝 지점에 설정해두고, 각 반복문의 sum의 결과에 따라서 포인터를 이동하고,
sum과 target이 일치함과 동시에 start포인트와 end포인트가 좋은 수 자신이 아닐 경우에 count에 1을 증가시키고 반복문을 종료한다.