[백준] 14921 : 용액 합성하기 (JAVA)

난이도

🥇 5

 

링크

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

14921번: 용액 합성하기

---

문제

---

풀이과정

해당 문제는 투 포인터를 사용하는 문제이다.

 

이분탐색과 비슷한 형식이기 때문에 풀이 형식이 익숙하다.

맨 앞과 맨 뒤에 각각 2개의 포인터를 두고서 하나씩 움직이며 원하는 값을 얻어내면 된다.

 

해당 문제에서는 두 용액을 합성하여 0에 가장 가까운 값을 만드는 것이 핵심이었기에 

1) 투 포인터를 사용하여 우선 맨 앞과 맨 뒤의 2개의 용액을 선택한다.

2) 만약 두 용액의 합이 음수라면

    ➡️ 오름차순 배열이기 때문에 왼쪽 포인터를 오른쪽으로 옮긴다.

    ➡️ 0에 가깝게 만드려면 음수 값을 최소한으로 만들어야 하기 때문!

3) 만약 두 용액의 합이 양수라면 

    ➡️ 오른쪽 포인터를 왼쪽으로 옮긴다.

    ➡️ 양수의 값을 줄여 0에 가깝게 만드는 것!

4) 만약 두 용액의 합이 0이라면

    ➡️ 원하는 값을 얻어냈기에 while문을 종료한다

5) 위의 과정을 거치기 전에 이전의 합보다 현재의 합이 더 작은 경우는 결과값을 갱신해야한다!

 

🚨 while 문에서 조건 설정 시 left와 right 값이 같으면 안되기 때문에 꼭 left < right 로 설정해야 한다!

---

전체 코드

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[] solution = new int[N];

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

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

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

        long result = Integer.MAX_VALUE;

        while (left < right) {
            long sum = solution[left] + solution[right];

            if (Math.abs(sum) < Math.abs(result)) {
                result = sum;
            }

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

        System.out.println(result);
    }
}

 

결과