[백준 - 1253] 좋다 .java

https://www.acmicpc.net/problem/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

 

 

Solution

<문제 분석>

좋은 수(다른 두 수의 합으로 표현되는 수)를 하나 찾는 알고리즘의 시간 복잡도는 최소  O(nlogn)이어야 한다.

즉, 정렬이나 투 포인터 알고리즘을 사용해야 한다. 투 포인터 연습을 위해 이걸로 풀었다.

 

먼저 투포인터를 사용하기 위해 정렬을 해준다.

판별하는 수인 d가 1~10까지의 범위이며 이를 for문으로 검사한다.

하지만 이 d는 포인터의 값이며 안되기 때문에 조건을 통해 확인해줘야 한다.

즉, 두 포인터의 합이 d와 같고 이때 d 값에 해당하는 인덱스를 포인터 값으로 가지면 안 된다.

만약 합이 같은데 d값의 해당하는 인덱스가 포인터 값이라면 포인터를 하나씩 이동시켜 주면 된다.

참고~

<코드>

위 설명과 다르게 d를 그냥 인덱스 변수로 사용하였고  find 변수를 d인덱스의 값으로 설정하였다.

나머지는 동일하다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        // 입력을 받을 BufferedReader 객체 생성
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 첫 번째 줄에서 배열의 크기 n 입력
        int n = Integer.parseInt(br.readLine());

        // 두 번째 줄에서 배열 E 입력
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] E = new int[n];
        for (int i = 0; i < n; i++) {
            E[i] = Integer.parseInt(st.nextToken());
        }

        // 배열 정렬
        Arrays.sort(E);

        // "좋은 수"의 개수를 셀 변수
        int count = 0;

        // 배열의 각 원소를 타겟으로 설정하여 반복
        for (int d = 0; d < n; d++) {
            int find = E[d];  // 현재 타겟이 되는 수
            int l = 0;        // 왼쪽 포인터
            int r = n - 1;    // 오른쪽 포인터

            // 두 포인터가 겹치지 않을 때까지 반복
            while (l < r) {
                // 두 수의 합이 타겟 수와 같을 때
                if (E[l] + E[r] == find) {
                    // 두 포인터가 타겟 수를 가리키지 않는 경우
                    if (l != d && r != d) {
                        count++;
                        break;
                    } else if (l == d) {
                        l++;
                    } else if (r == d) {
                        r--;
                    }
                } 
                // 두 수의 합이 타겟 수보다 작은 경우
                else if (E[l] + E[r] < find) {
                    l++;
                } 
                // 두 수의 합이 타겟 수보다 큰 경우
                else {
                    r--;
                }
            }
        }

        // 결과 출력
        System.out.println(count);

        // BufferedReader 닫기
        br.close();
    }
}