[백준] 3273번 - 두 수의 합 [Java]

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

 

[백준] 3273번 - 두 수의 합 [Java]

---

1.  아이디어

 

투 포인터 알고리즘을 활용하면 간단하게 해결할 수 있다.

---

2. 문제풀이

 

두 수의 합이 X가 되는 조합의 수를 구해야 한다.

이를 투 포인터 알고리즘을 적용하면 입력 값을 배열로 저장한 뒤 정렬을 해준다.

이후 배열 양 끝에서 포인터를 출발해서 두 수의 합이 X보다 작으면 왼쪽 포인터를 오른쪽으로 한 칸 이동시켜 두 수의 합이 더 커지게 만들고 두 수의 합이 X보다 크면 오른쪽 포인터를 왼쪽으로 한 칸 이동시켜 두 수의 합이 더 작아지게 만들어준다. 두 수의 합이 X가 되면 조합의 수를 하나 세고 두 포인터를 모두 한 칸씩 이동시키면 된다.

---

3. 코드

 

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

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

        int N = Integer.parseInt(br.readLine());

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

        int X = Integer.parseInt(br.readLine());

        int left = 0;
        int right = N - 1;
        int cnt = 0;

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

            if (sum < X) {
                left++;
            } else if (sum > X) {
                right--;
            } else {
                left++;
                right--;
                cnt++;
            }
        }

        System.out.println(cnt);
    }
}

---

4. 후기