[백준] 2470: 두 용액 - Java (Two Pointer)

  목 차

• 문제
• 접근 방식
• 풀이

 

---

  문제

 

 

 

 

  접근 방식

 

이 문제는 투 포인터를 활용하여 알고리즘을 구현하는 문제이다. 

투포인터의 특성상 대부분의 문제가 정렬을 요구하는데, 자바에서는 Arrays.sort(배열)를 사용하면 쉽게 정렬을 할 수 있다. 우리의 요점은 정렬이 아닌 투 포인터 기법이니 가볍게 넘어가기로 했다.

 

왼쪽과 오른쪽에 포인터를 하나씩 놔두고 조건에 따라 각각 한 칸씩 오른쪽과 왼쪽으로 이동하게 한다.

 

먼저 다음과 같이 구현순서를 정의했다.

1. 두 포인터가 가리키는 값의 합을 더한다. (sum = arr[left] + arr[right])

2. 이전까지 가장 가까웠던 거리의 크기와 현재 거리의 크기를 비교한다.

    2 - 1. 현재 거리의 크기가 더 작다면 값을 갱신해준다.

    2 - 2. 현재 거리의 크기가 더 크다면 그냥 넘어간다.

3. 더한 값 확인

    3 - 1. 더한 값이 0 보다 크다면 오른쪽 포인터를 왼쪽으로 한 칸 이동.

    3 - 2. 더한 값이 0 보다 작다면 왼쪽 포인터를 오른쪽으로 한 칸 이동.

 

이렇게 구현하면 빠르게 문제를 풀 수 있다.

 

 

  풀이

 

package src.TwoPointer;

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

public class 두용액_2470 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        int[] arr = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine());

        for(int i = 0; i < n; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(arr);

        int left = 0;
        int right = n - 1;

        int value_l = 0;
        int value_r = 0;

        int result = Integer.MAX_VALUE;

        while(left < right){

            int sum = arr[left] + arr[right];

            if(Math.abs(result) > Math.abs(sum)){
                result = sum;
                value_l = arr[left];
                value_r = arr[right];
            }

            if(sum > 0){
                right --;
            } else {
                left ++;
            }

        }

        StringBuilder sb = new StringBuilder();

        if(value_l >= value_r){
            sb.append(value_r).append(" ").append(value_l);
        } else {
            sb.append(value_l).append(" ").append(value_r);
        }

        System.out.println(sb);


    }
}