[JAVA] 2467 용액, 14921 용액합성하기, 2473 세 용액

2467 용액

#소스코드

: 모든용액에 대하여 한가지를 잡고, 나머지 한 용액은 이분탐색으로 찾음.

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] lq = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            lq[i] = Integer.parseInt(st.nextToken());
        }
        int max = Integer.MAX_VALUE;

        int[] ans = new int[2];

        for (int i = 0; i < lq.length; i++) {//lq[i]값에 대하여 나머지 하나의 용액선택
            int left = i + 1;//현재 용액 다음~끝까지 이분탐색
            int right = lq.length - 1;

            while (left <= right) {
                int mid = (left + right) / 2;

                int sum = lq[i] + lq[mid];

                if (Math.abs(sum) < max) {
                    ans[0] = lq[i];
                    ans[1] = lq[mid];
                    max = Math.abs(sum);
                }

                if (sum < 0) left = mid + 1;
                else right = mid - 1;
            }
        }
        System.out.println(ans[0] + " " + ans[1]);
    }
}

 

14921 용액합성하기

#소스코드

: sum값을 각각에 대하여 절대값을 비교하여 리턴한다.

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] lq = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            lq[i] = Integer.parseInt(st.nextToken());
        }
        int max = Integer.MAX_VALUE;

        for (int i = 0; i < lq.length; i++) {//lq[i]값에 대하여 나머지 하나의 용액선택
            int left = i + 1;//현재 용액 다음~끝까지 이분탐색
            int right = lq.length - 1;

            while (left <= right) {
                int mid = (left + right) / 2;

                int sum = lq[i] + lq[mid];
                //위 부분까지는 <용액 2467>문제와 동일하지만 둘다 절대값으로 비교해줘야함
                if (Math.abs(sum) < Math.abs(max)) {
                    max = sum;
                }

                if (sum < 0) left = mid + 1;
                else right = mid - 1;
            }
        }
        System.out.println(max);
    }
}

 

2473 세 용액

#소스코드

: 자료형에 유의해야 하는 문제이다. n^2 * log n 으로 풀리는 문제이다.

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        long[] lq = new long[n];//<----------얘는 왜 long이어야 될까요?
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            lq[i] = Long.parseLong(st.nextToken());
        }
        Arrays.sort(lq);
        long max = Long.MAX_VALUE;

        long[] ans = new long[3];
        for (int i = 0; i < lq.length-1; i++) {//lq[i]값에 대하여 나머지 하나의 용액선택
            for (int j = i + 1; j < lq.length; j++) {//lq[j]값에 대하여 나머지 하나의 용액선택
                int left = j + 1;//현재 용액 다음~끝까지 이분탐색
                int right = lq.length - 1;

                while (left <= right) {
                    int mid = (left + right) / 2;

                    long sum = lq[i] + lq[j] + lq[mid];//<-----여기서 오버플로우일까요??
                    if (Math.abs(sum) < max) {
                        ans[0]=lq[i];
                        ans[1]=lq[j];
                        ans[2]=lq[mid];
                        max = Math.abs(sum);
                    }

                    if (sum < 0) left = mid + 1;
                    else right = mid - 1;
                }
            }
        }
        Arrays.sort(ans);
        System.out.println(ans[0] + " " + ans[1] + " " + ans[2]);
    }
}