[백준/JAVA] 2470번: 두 용액

🔺 문제

2470번: 두 용액

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
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());
        
        long[] A = new long[N];
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0 ; i < N ; i++) {
            A[i] = Long.parseLong(st.nextToken());
        }
        
        Arrays.sort(A);    // 🔔 투 포인터 실행 전 정렬 필수!
        
        // 투 포인터
        long gap = Integer.MAX_VALUE;
        
        int s = 0;
        int e = N - 1;
        
        long ans1 = 0;
        long ans2 = 0;
        
        while(s < e) {
            long sum = A[s] + A[e];
            long absSum = Math.abs(sum);
            
            if(absSum < gap) {
                gap = absSum;
                ans1 = A[s];
                ans2 = A[e];
            }   
                
            if(sum < 0) {
                s++;
            }
            else {
                e--;
            }
        }
 
        System.out.println(ans1 + " " + ans2);
    }
}
 

✅ 해결 아이디어
✔ 투 포인터 (시간 복잡도 : O(N))

 

💥 유의사항

• 완전탐색으로 했다간 크기 때문에 시간 초과 뜬다...

 

 

---

🔺 다른 풀이들

- 이진 탐색 활용한 풀이

[ baekjoon ] 두 용액 2470번 ( Java )

---

💬 느낀 점

이진 탐색이랑 투 포인터랑 머릿속에서 약간 섞여서 혼란스러웠다(?)

 

 

 

1회독	2회독	3회독	4회독	5회독
V	12.2	240222

 

 

(+12.2 2회독)

입력받은 값을 절댓값 기준 오름차순 정렬하고, (O(NlogN))

현재 값과 다음 값의 특성값을 구한다.

이 값이 기준 특성값보다 작다면 기준 특성값을 갱신하고, 정답도 갱신한다.

 

특성값도 배열로 받아 오름차순으로 정렬 후 출력한다.

 

코드 확인하기

import java.util.*;
import java.io.*;
 
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());
        Liquid[] arr  = new Liquid[N];
        
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0 ; i < N ; i++) {
            arr[i] = new Liquid(Integer.parseInt(st.nextToken()));
        }
        Arrays.sort(arr);   // 사용자 정의 정렬
        
 
        int[] answer = new int[2];
        int diff = Integer.MAX_VALUE;
        
        for(int i = 0 ; i < N - 1 ; i++) {
            if(Math.abs(arr[i].val + arr[i + 1].val) < diff) {
                answer[0] = arr[i].val;
                answer[1] = arr[i + 1].val;
                
                diff = Math.abs(arr[i].val + arr[i + 1].val);
            }
        }
        
        Arrays.sort(answer);    // 특성값 오름차순 정렬
        System.out.println(answer[0] + " " + answer[1]);
        
    }
}
 
class Liquid implements Comparable<Liquid> {
    int val;
    
    public Liquid(int val) {
        this.val = val;
    }
    
    // 절댓값 기준 오름차순 정렬
    @Override
    public int compareTo(Liquid o) {
        return Math.abs(this.val) - Math.abs(o.val);
    }
}
 

---

(참고)

[알고리즘] 백준 2470 두 용액 -투포인터- 자바