[백준] 1253번 : 좋다 Gold4(골드4) - JAVA[자바]

[Gold IV] 좋다 - 1253

문제 링크

성능 요약

메모리: 12688 KB, 시간: 124 ms

분류

이분 탐색, 자료 구조, 정렬, 두 포인터

제출 일자

2024년 6월 18일 00:30:07

문제 설명

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

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

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

입력

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

출력

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

 

접근 방법

1. 각 값에 대하여 투 포인터를 사용하기 위해서 정렬한다.(n log n)

2. 그 후 차례대로 값을 확인하면서 그 값이 좋다수인지 확인해준다.( n )

3. 투포인터를 이용해서 확인하되 해당 값이 확인해주는 인덱스인지 아닌지 확인해줘야 함( n )

-> n 은 최대 2,000임으로 n * n인 4,000,000으로 안전하게 풀이 가능하다.

 

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

/**
 * 30분 컷
 */
public class BOJ_1253 {
    static int[] arr;
    static int N;

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

        // Input
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }// Input End
        Arrays.sort(arr);

        int answer = 0;
        for (int i = 0; i < N; i++) {
            // 좋다수면 증가
            if (check(i)) {
                answer++;
            }
        }
        System.out.println(answer);
    }

    private static boolean check(int idx) {
        int l = 0, r = N - 1;
        int checkNum = arr[idx];
        while (l < r) {
            int sum = arr[l] + arr[r];
            // 좋다수인지 확인하는 값이라면 증가 시켜준다.
            if (l == idx || sum < checkNum) {
                l++;
            } else if (r == idx || sum > checkNum) {
                r--;
            }
            // 위 조건 분기 둘 다 해당 안될 시 좋다 수
            else {
                return true;
            }
        }
        // 좋다수가 아닌 경우
        return false;
    }
}