[백준 2467번] 용액 - JAVA

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

2467번: 용액

풀이

사용한 알고리즘 : 이진 탐색, 우선순위 큐

 

풀이전략

보통의 이진 탐색에서는 mid(=(start+end)/2)를 사용하여 중간 값 기준으로 start와 end 위치를 변경한다.

하지만 이 문제 풀이에서는 중간 값이 아닌

양 끝의 범위를 양 끝에서 점점 조이는 방법을 활용하되 이진 탐색 구현 코드를 일부 사용했다.

 

양 끝 값의 합을 구하고, 그 값이 기존의 합 중 가장 작은 값보다 작으면

이번 연산에서의 합을 가장 작은 값으로 변경한다.

또한 합산에 사용된 양 끝 값을 저장해둔다.

 

만약 양 끝 값의 합이 0보다 큰 경우엔,더 작은 값을 구하기 위해 끝점을 1 더 앞당긴다. ( end = end-1 )

 

반대로 양 끝 값의 합이 0보다 작은 경우엔더 큰 값을 구하기 위해 시작점을 1 뒤로 미룬다. ( start = start +1 )

 

위 과정을 start>=end 가 될 때까지 반복하고그 때 저장해뒀던 양 끝 값의 합산이 가장 작은 경우의 양 끝 값을 출력하면 정답이 도출된다.

 

 

제출코드

1. 이진 탐색을 사용한 코드

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

public class Main {

    static int list[];
    static int minDiff = 2000000001;
    static int firstVal=0;
    static int secondVal=0;
    static void binarySearch(int start,int end){
        while(start<end){
            int absSum=Math.abs(list[start]+list[end]);
            if(absSum<minDiff){
                firstVal=list[start];
                secondVal=list[end];
                minDiff=absSum;
            }

            if(list[start]+list[end]==0) break;
            else if(list[start]+list[end]>0){
                --end;
            }
            else ++start;
        }
    }
    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());

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

        binarySearch(0,N-1);

        bw.write(firstVal+" "+secondVal+"\n");
        bw.flush();
        bw.close();
    }
}

 

2. 우선순위 큐를 사용한 코드

import java.io.*;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

    static class Node implements Comparable<Node>{
        int sign;
        int number;

        public Node(int sign,int number){
            this.sign=sign;
            this.number=number;
        }
        @Override
        public int compareTo(Node o) {
            if(this.number<o.number) return -1;
            else return 1;
        }
    }

    static PriorityQueue<Node> q = new PriorityQueue<>();
    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        for(int i=0;i<N;++i){
            int num = Integer.parseInt(st.nextToken());
            int sign;

            if(num<0) sign=-1;
            else sign=1;

            Node node = new Node(sign, num*sign);
            q.offer(node);
        }

        int answer = (int)1e11;
        Node pre = q.poll();

        int first=0;
        int second=0;
        for(int i=1;i<N;++i){
            Node now = q.poll();
            int diff = Math.abs(now.number*now.sign+
                    pre.number*pre.sign);
            if(answer>diff){
                answer=diff;
                first=pre.number*pre.sign;
                second=now.number*now.sign;
                //System.out.println(first+" "+second);
            }
            answer = Math.min(answer,diff);
            pre=now;
        }

        if(first<second) bw.write(first+" "+second+"\n");
        else bw.write(second+" "+first+"\n");

        bw.flush();
        bw.close();
    }
}

 

이분 탐색을 사용했을 때 416ms, 우선순위 큐를 사용했을 때 496ms로

이분 탐색이 조금 더 빨랐다.