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

 

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

14921번: 용액 합성하기

1. 문제 설명

 

문제

• 두 용액을 섞어서 0에 가장 가까운 용액을 만들려고 한다.
• N(2 <=N <=100,000) 개의 용액이 주어진다.
• -100,000,000 <=용액 <=100,000,000

출력

• 두 용액을 섞어서 만들 수 있는 0에 가장 가까운 용액의 특성 값 출력

 

2. 풀이

 

투 포인터로 풀 수 있다.

 

완전 탐색으로 풀게 된다면 N^2(100,000^2)으로 시간 초과가 발생할 수 있다.

 

하지만, 투 포인터로 풀게 된다면 N으로 빠르게 문제를 풀 수 있다.

 

투 포인터 문제의 경우 정렬이 필수적인데, 이 문제의 경우 용액들의 특성 값이 오름차순으로 주어지므로, 정렬을 할 필요가 없다.

 

처음에 answer 초기 값은 200,000,001로 설정해주었는데, 용액의 최대 특성값이 100,000,000이기에 용액의 최대 특성 값 *2+1로 설정해 주었다.

 

 

*로직

- left 0, right n-1부터 탐색 시작

- left 용액의 특성 값과 right 용액의 특성 값을 합친 것이 0이라면 탐색 종료 

- left 용액의 특성 값과 right 용액의 특성 값을 합친 것이 기존 answer보다 작다면 answer update

- left 용액의 특성 값과 right 용액의 특성 값을 합친 것이 0보다 작다면 left 인덱스 증가 (left를 증가시킬수록 숫자가 크다.)

- left 용액의 특성 값과 right 용액의 특성 값을 합친 것이 0보다 크다면 right 인덱스 감소 (right를 감소시킬수록 숫자가 작다)

 

3. 코드

// JAVA 11, 시간 340ms, 메모리 24344KB

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

public class Main {



    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int num, left, right;
        int[] list;
        int answer = 200000001;

        num = Integer.parseInt(br.readLine());

        list = new int[num];

        left = 0;
        right = num - 1;

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

        for (int x = 0; x < num; x++) {
            list[x] = Integer.parseInt(st.nextToken());
        }

        // 투포인터
        while (left < right) {

            if (list[left] + list[right] == 0) {
                answer = 0;
                break;
            }

            if (Math.abs(answer) > Math.abs(list[left] + list[right])) {
                answer = list[left] + list[right];
            }

            if (list[left] + list[right] > 0) {
                right--;
            } else {
                left++;
            }
        }

        bw.write(String.valueOf(answer));
        bw.flush();

    }



}