[백준 2470번] 두 용액 (Java 풀이)

백준알고리즘 2470번 : 두 용액 (Solved.ac 난이도 Gold5)

여러 용액 중 그 합의 절댓값이 가장 작은 두 용액을 찾아내는 문제이다.

 

2차원 배열로 값을 담아 for문을 한 번 돌면서 그 합이 가장 낮은 숫자 들을 찾는다.

 

↑클릭시 문제 link로 이동합니다.😊

 

 

시간 제한이 1초라서
        
이중 for문으로 돌리면 무조건 시간초과가 날 것 같았다.

그래서 떠올린 방법이 2차원 배열로 값을 담되, 값을 담으면서 음수는 미리 check해두는 것이다.

절댓값으로 정렬하고 난 뒤에 for문을 한번만 돌면서 i번째와 i+1번째 값을 비교한다.

이 두 숫자의 합이 가장 작은 경우를 찾는다.
(절대값으로 처리된 숫자로는 정확한 합을 구할 수 없기 때문에 양/음수를 check해둔 값을 불러와서 실제 숫자를 호출하여 계산해야한다.)

합이 0이되면 그 즉시 break한다.

가장 작았던 때의 숫자들의 위치를 기억한 뒤에 해당 값들을 출력한다.

 

풀이 과정

---

1. 숫자들을 2차원 배열로 담되 1열에는 절대값을, 2열에는 양/음수 여부를
   check하는 숫자(1,-1)를 담는다.
2. 2차월 배열을 1열 절대값을 기준으로 오름차순 정렬한다.
3. 배열 길이-1 만큼 돌면서 그 합이 가장 낮은 위치를 check한다.
4. check된 숫자들을 오름차순으로 출력한다.

 

 

 

소스 ▽

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Main { // [Gold5] 2470번 : 두 용액
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int testCase = Integer.parseInt(br.readLine());
        int[][] num = new int[testCase][2];
        StringTokenizer st = new StringTokenizer(br.readLine());
        int x = 0;
        for (int i = 0; i < testCase; i++) {
            x = Integer.parseInt(st.nextToken());
            if (x < 0) {
                num[i][0] = Math.abs(x);
                num[i][1] = -1;
            } else {
                num[i][0] = x;
                num[i][1] = 1;
            }
        }
        Arrays.sort(num, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });

        int pos = 0;
        int min = 2000000000;
        int tmp;
        for (int i = 0; i < num.length - 1; i++) {
            tmp = num[i + 1][0] * num[i + 1][1] + num[i][0] * num[i][1];
            if (Math.abs(tmp) < Math.abs(min)) {
                min = tmp;
                pos = i;//최소차이를 갖고있는 곳의 pos
                if (min == 0) {
                    break;
                }
            }
        }

        int num1 = num[pos][0] * num[pos][1];
        int num2 = num[pos + 1][0] * num[pos + 1][1];
        if (num1 < num2) {
            System.out.println(num1 + " " + num2);
        } else {
            System.out.println(num2 + " " + num1);
        }
    }
}