[BOJ/GoldⅣ] 1253. 좋다 - JAVA 자바

1253번: 좋다

• 144ms
• 투포인터

단순히 이중 for문으로 풀었을 때, 시간초과가 발생했다. 두 수를 선택해서 푸는 문제이므로 투포인터가 떠올랐다.

 

1부터 n까지 좋은 수인지 투포인터를 통해 합이 되는 경우가 있는지 탐색한다.

 

left = 0, right = n - 1 을 초기값으로 잡은 후,

1. left 가 arr[i] 이면 오른쪽으로 한 칸 이동 left++
2. right 가 arr[i]이면 왼쪽으로 한 칸 이동 right--
3. arr[left] + arr[right] == arr[i] 이면 좋은 수이므로 count 증가
4. arr[left] + arr[right] 이 arr[i]보다 작으면 합을 키워야 하므로 오른쪽으로 한 칸 이동 left++
5. arr[left] + arr[right] 이 arr[i]보다 크면 합을 줄여야 하므로 왼쪽으로 한 칸 이동 right--

import java.util.*;
import java.io.*;

public class Main {

    static int n, result, arr[];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        n = Integer.parseInt(br.readLine());

        st = new StringTokenizer(br.readLine());
        arr = new int[n];
        for (int i = 0; i < n; i++)
            arr[i] = Integer.parseInt(st.nextToken());

        Arrays.sort(arr);

        for (int i = 0; i < n; i++) {
            int left = 0;
            int right = n - 1;

            while (left < right) {
                if (left == i) left++;
                else if (right == i) right--;
                else {
                    int sum = arr[left] + arr[right];
                    if (sum == arr[i]) {
                        result++;
                        break;
                    }

                    if (sum < arr[i]) left++;
                    else right--;
                }
            }

        }

        System.out.println(result);
    }
}