투포인터 백준 #2257번 <자바>

문제 해석!

1. 용액 2개를 구분하기 위해 특성값이 있다.

2. 산성은 양의 정수 / 알칼리성은 음수의 정수다.

3. 혼합한 용액의 특성값은 각 용액의 특성값의 합으로 정의

4. 이 때, 특성 값이 0에 가깝게 만들고 싶다.

 

문제를 딱 보고 든 생각?!

1. 리스트를 이용해야겠구나

2. 리스트를 접근하기 위해 두 값의 위치를 기록할 필요가 있다.

-> 아 투포인터 알고리즘을 활용하자

 

문제의 특수 상황

특정한 값인 0에 가깝도록 하는 값 찾기

 

아이디어

1. 첫번째 인덱스가 마지막 인덱스보다 작을 때까지 계속 반복

1-1. 만약 차이가 임시값보다 크면 값을 서로 치환

1-2. 합이 0보다 크면 마지막 인덱스를 줄이고, 합이 0보다 작으면 첫번째 인덱스를 늘리자

 

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());

        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 firstIdx = 0;
        int lastIdx = N - 1;
        int gap = Integer.MAX_VALUE;
        int ans1 = 0;
        int ans2 = 0;

        int tmp;
        int sum;

        while (firstIdx < lastIdx) {
            sum = arr[firstIdx] + arr[lastIdx];
            tmp = Math.abs(sum);

            if(gap > tmp){
                ans1 = arr[firstIdx];
                ans2 = arr[lastIdx];
                gap = tmp;
            }

            if(sum > 0){
                lastIdx--;
            }else{
                firstIdx++;
            }
        }

        System.out.println(ans1 + " " + ans2);
    }
}

코테에서 자주 나오는 구문

StringTokenizer : 쪼개서 입력받기

쪼개서 받은 문자를 리스트에 저장할 때 -> for문 자주 나옴!! 따로 암기하면 많이 유용함