BOJ 14921 : 용액 합성하기

·2023년 1월 21일
0

알고리즘 문제 풀이

목록 보기
43/165
post-thumbnail

문제

풀이 과정

요약

투 포인터를 활용한 용액 문제.

상세

  1. 입력값이 오름차순으로 주어진다에 주목하자.
  2. 현재 입력값의 최대 최소를 기점으로 하여, 0 에 가까운 용액의 합을 찾는다. l,rl, r
  3. rr 을 예로 들어보자. 현재 두 용액의 합이 xx 라면, rr 이 작아질 수록 xx 역시 점점 작아지게 된다. 본 문제는 0 에 가까운 값을 찾는 것이므로, xx 가 0보다 큰 경우라면 지속적으로 rr 을 줄인다.
  4. ll 을 예로 들어보자. 현재 두 용액의 합이 xx 라면, ll 이 커질 수록 xx 는 점점 커지게 된다. 본 문제는 0 에 가까운 값을 찾는 것이므로, xx 가 0보다 작은 경우라면 지속적을 ll을 키운다.
  5. 3~4의 과정을 매 상황마다 반복하면 0 혹은 현재 배열에서 0에 가장 가까운 용액의 합을 찾을 수 있다.

정답

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

public class Main {
    static int[] arr;
    static int N;
    static int ans = 987654321;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new int[N];
        StringTokenizer stk = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) arr[i] = Integer.parseInt(stk.nextToken());
        int l = 0;
        int r = arr.length - 1;

        while (l < r) {
            int val = arr[l] + arr[r];
            if(Math.abs(ans) > Math.abs(val)) ans = val;
            if (val == 0) break;
            else if (val > 0) r--;
            else l++;
        }

        System.out.println(ans);
    }
}
profile
새로운 것에 관심이 많고, 프로젝트 설계 및 최적화를 좋아합니다.

0개의 댓글