[백준] G4 1253번 좋다 (Java)

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

해당 문제는 'Do it! 알고리즘 코딩테스트 자바 편'을 보면서 공부한 내용입니다.

👉 문제

투 포인터 알고리즘을 사용한다고 하는데, 단순히 두개의 인덱싱을 제어한다고 생각하면 될 것 같다.

1. 입력받는 N개의 수를 배열에 저장한 후 정렬한다.

2. 투 포인터 i, j를 배열 arr 양쪽 끝에 위치시키고 조건에 적합한 투 포인터 이동 원칙을 활용해 탐색을 수행한다. 판별의 대상이 되는 수는 k라고 가정한다.

   투 포인터 이동 원칙
   - arr[i] + arr[j] > K: j--;
     arr[i] + arr[j] < K: i++;
   - arr[i] + arr[j] == K: i++; j--; count++;	// 프로세스 종료

3. 2단계를 배열의 모든 수에 대하여 반복한다. 즉, K가 N이 될 때까지 반복하며 좋은 수가 몇 개인지 세는 것이다.

👉 풀이

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

public class _1253_1 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int Result = 0;
        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);

        for (int k = 0; k < N; k++) {
            long find = arr[k];
            int i = 0;
            int j = N - 1;

            // 투 포인터 알고리즘
            while (i < j) {
                if (arr[i] + arr[j] == find) {
                    // find는 서로 다른 두 수의 합이어야 함을 체크
                    if (i != k && j != k) {
                        Result++;
                        break;
                    } else if (i == k) {
                        i++;
                    } else if (j == k) {
                        j--;
                    }
                } else if (arr[i] + arr[j] < find) {
                    i++;
                } else {
                    j--;
                }
            }
        }
        System.out.println(Result);
        br.close();
    }
}

👉 성능