[백준] 3273 두 수의 합 - Java

문제

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

3273번: 두 수의 합

문제 풀이

문제 분류에서도 정렬과 두 포인터로 분리되어 있고, 문제를 들어가면서도 투 포인터를 써보라고 하여 투 포인터를 이용하여 문제를 풀어보려 한다.

문제의 조건은 백준에서의 예제로 한다.

9
5 12 7 10 9 1 2 3 11
13

투 포인터를 사용하기 위해선 일단 배열을 정렬된 상태로 만들어줘야 한다.

그림과 비교하며 보기에는 오름차순으로 정렬하는게 좋을 것 같아 오름차순으로 정렬함.

정렬된 상태를 만들었으면 두 개의 포인터를 설정한다.

두 개의 포인터를 설정하였으면 두 포인터가 한 지점이 될 때 까지 다음 질의를 반복한다.

• start point + end point > x 인가?
  • x보다 크기때문에 숫자를 줄여야 한다. 따라서 end point를 왼쪽으로 한 칸 옮긴다.
• start point + end point < x 인가?
  • x보다 작기때문에 숫자를 증가시켜야 한다. 따라서 start point를 오른쪽 한 칸 옮긴다.
• start point + end point == x 인가?
  • 한 쌍을 구하였기 때문에 start point를 오른쪽으로 한 칸, end point를 왼쪽으로 한 칸 옮긴다.
  • 한 쌍에 대한 count는 따로 세도록 한다.

코드 1. 위의 풀이 방식을 그대로 구현

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

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());
        int x = Integer.parseInt(br.readLine());
        
        // 배열 생성
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        // 배열 정렬
        Arrays.sort(arr);

        int startPoint = 0;
        int endPoint = n - 1;
        int count = 0;
        int temp = 0;
        
        // start point와 end point가 만날 때까지 반복
        while (startPoint < endPoint) {
            temp = arr[startPoint] + arr[endPoint];
            // start point + end point > x ?
            if (temp > x) {
                // end point 왼쪽으로 한 칸 이동
                endPoint--;
            }
            // start point + end point < x ?
            else if (temp < x) {
                // start point 오른쪽으로 한 칸 이동
                startPoint++;
            }
            // start point + end point == x ?
            else {
                // start point 오른쪽으로, end point 왼쪽으로 한 칸씩 이동
                startPoint++;
                endPoint--;
                count++;
            }
        }
        System.out.println(count);
        br.close();
    }
}