[Java] 백준_좋다_1253

문제

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

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

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

 

입력

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

 

출력

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

 

예시

분석

좋은 수가 되려면 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있어야 한다. 예를들어 N이 3이고 1 2 3을 입력받는다고 가정하자. 3은 다른 두 수 1과2의 합으로 나타할 수 있으므로 좋은 수라고 할 수 있다. 로직을 생각한다면 갯수 N을 입력받은 다음에 각 요소에 접근해서 좋은 수 있지 판단하면 된다. 

 

시간복잡도는 단순 완전 탐색을 할 경우에는 O(N^3)이 된다. 데이터의 크기 N이 최대 2000이므로 80억(80초)이 되므로 시간복잡도를 낮춰야한다. 투포인터 알고리즘을 이용하면 서로 다른 두 수를 선택하는 시간 복잡도가 O(N)이 되고 결국 최종 시간복잡도는 O(N^2)이 되어 제한시간 2초안에 문제를 풀 수 있다.

 

큰 흐름은 다음과 같다.

- N을 입력받은 후 N개의 요소를 입력받는다. 

- N개의 요소를 정렬한다.

- for문을 사용해서 각 요소에 차례대로 접근한다.

- 투포인터 알고리즘을 사용하기 위해 start = 0, end = N-1 2가지 포인터를 선언한다.

- while(start < end)

- 어떤 수는  다른 두 수는 서로 다른 수이어야 하므로 start또는 end 인덱스 값이 어떤 수에 해당하는 인덱스면 인덱스를 바꿔준다.

- 두 수의 합이 접근한 요소와 같다면 count++

- 두 수의 합이 접근한 요소보다 크다면 end--

- 두 수의 합이 접근하 요소보다 작다면 start++

 

소스코드

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

public class 좋은수구하기_008 {

    static int N;
    static long[] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new long[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Long.parseLong(st.nextToken());
        }
        Arrays.sort(arr);
        int goodNumCount = 0;
        for (int i = 0; i < N; i++) {
            if(isGoodNum(i))
                goodNumCount++;
        }
        System.out.println(goodNumCount);
        br.close();
    }

    public static boolean isGoodNum(int index) {
        long find = arr[index];
        int start = 0;
        int end = N-1;
        while (start < end) {
            long sum = arr[start] + arr[end];
            if (start == index) {
                start++;
                continue;
            }
            if (end == index) {
                end--;
                continue;
            }

            if (find == sum) {
                return true;
            } else if (find < sum) {
                end--;
            } else if (find > sum) {
                start++;
            }
        }
        return false;
    }
}

 

결과