[JAVA] 백준 1253 좋다

 

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

 

문제분석

투 포인터 문제이다(백준에는 투포인터 대신 '두 포인터' 라고 표현되어있다).

 

이 문제는 정렬과 투 포인터를 활용해 특정 수가 배열 내 다른 두 수의 합으로 표현 가능한지를 판별하는 방식이다. 먼저 입력값을 배열에 저장한 뒤 오름차순 정렬한다. 이후 각 인덱스 i를 기준으로 arr[i]를 목표값(target)으로 설정하고, 배열의 양 끝에서 시작하는 두 포인터(left, right)를 이용해 합을 탐색한다. 기본 아이디어는 left와 right가 가리키는 두 수의 합이 target과 같은지를 비교하면서 범위를 좁혀가는 것이다.

단, 자기 자신을 두 번 사용하는 경우를 배제해야 하므로 left나 right가 현재 기준 인덱스 i와 같다면 포인터를 이동시켜 건너뛴다. 두 수의 합이 target보다 작으면 left를 증가시키고, 크면 right를 감소시켜 탐색 범위를 조정한다. 합이 정확히 일치하고 두 포인터 모두 i와 다르면 해당 값은 조건을 만족하는 것이므로 결과를 증가시키고 탐색을 종료한다. 이렇게 모든 원소에 대해 반복하면, 배열에서 다른 두 수의 합으로 표현 가능한 값의 개수를 효율적으로 구할 수 있다.

 

 

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        long result = 0;

        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            int target = Integer.parseInt(st.nextToken());
            arr[i] = target;
        }
        Arrays.sort(arr);

        for (int i = 0; i < N; i++) {
            int target = arr[i]; // 찾고자 하는 값
            int left = 0;
            int right = N - 1;

            while (left < right) {
                int sum = arr[left] + arr[right];

                if (sum == target) {
                    if (left == i) {
                        left++;
                    } else if (right == i) {
                        right--;
                    } else {
                        result++;
                        break;
                    }
                } else if (sum < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }

        System.out.println(result);
    }
}