[BOJ/Two Pointers] 백준 1253 - 좋다 (Java)

1253 - 좋🤙다👍

https://www.acmicpc.net/problem/1253

문제

N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 좋다(GOOD)고 함
=> N개 수가 주어지면 그 중에서 좋은 수의 개수 몇 개?
(수 위치 다르면 값이 같아도 다른 수)

입력
첫째 줄: 수의 개수 N (1 <= N <= 2,000)
두 번째 줄: i번째 수 나타내는 A_i가 N개 주어짐 (|A_i| <= 1,000,000,000, A_i는 정수)
출력: 좋은 수의 개수 

---

풀이

어떤 수 A[k]가 서로 다른 두 수 A[i] + A[j]로 표현되면 좋다

-> 두 수 합이  특정 값(target)이 되는 경우 => 투포인터 or 이분탐색 or 해시

 

수 범위: -10^9 ~ 10^9 => `long[] arr`

 

Two Pointers(투포인터)

• 투포인터는 정렬된 상태에서만 가능 -> `Arrays.sort(arr)`
  • 현재 합이 작으면 -> `lt++`
  • 현재 합이 크면 -> `rt--`
  • => 포인터를 한쪽으로 움직이면 결과가 단조롭게 변함 (단조성)
• 서로 다른 두 수의 합: i != j != k
  • `lt == k` -> `lt++`
  • `rt == k` -> `rt--`

for (int k = 0; k < N; k++) {
    long target = arr[k];
    int lt = 0;
    int rt = N - 1;

    while (lt < rt) {
        if (lt == k) {
            lt++;
            continue;
        }
        if (rt == k) {
            rt--;
            continue;
        }

        long sum = arr[lt] + arr[rt];
        if (sum == target) {
            cnt++;
            break;
        } else if (sum < target) lt++;
        else rt--;
    }
}

---

코드

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

// 좋다
public class boj_1253 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        long[] 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 cnt = 0;
        for (int k = 0; k < N; k++) {
            long target = arr[k];
            int lt = 0;
            int rt = N - 1;

            while (lt < rt) {
                if (lt == k) {
                    lt++;
                    continue;
                }
                if (rt == k) {
                    rt--;
                    continue;
                }

                long sum = arr[lt] + arr[rt];
                if (sum == target) {
                    cnt++;
                    break;
                } else if (sum < target) lt++;
                else rt--;
            }
        }

        System.out.println(cnt);
    }
}