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

www.acmicpc.net/problem/2470

2470번: 두 용액

 

 

백준 투포인터 유형에 있는 두 용액이라는 문제를 풀어봤습니다. ㅎㅎ

두 개의 용액을 골라 합이 0하고 가장 가까운 두 용액을 출력해주면 되는 문제입니다.

 

풀이방법을 간단히 설명하면 

1. 용액 배열 정렬

2. 양쪽 끝으로 투 포인터 탐색을 해주면 됩니다. 

가장 0하고 가까운 값이 나오면 정답을 갱신해주고 

둘의 차이가 양수면 오른쪽 포인터를 더 작은 값을 가진 왼쪽으로 움직음으로써 더 0에 가깝게 만들어주면 됩니다. (음수면 반대로 ㅇㅇ)

둘의 차이가 양수면 오른쪽 포인터를 더 작은 값을 가진 // 왼쪽으로 움직음으로써 더 0에 가깝게 만들어본다.

 

 

투 포인터에 정렬까지 필요한 문제는 처음 풀어봤네요.

 

투 포인터를 사용하면 배열를 한 번만 탐색하기 때문에, 리스트가 이미 정렬되어 있는 경우 O(n), 정렬되어 있지 않더라도 O(nlogn) 정도의 시간 복잡도로 문제를 해결할 수 있습니다. (참고로, 이분탐색일 경우는 O(logn) )

 

 

 

풀이는 다음고 같습니다.

 

[Java]

import java.util.Arrays;
import java.util.Scanner;

class Main {
    private static int N; //  2 이상 100,000 이하
    private static int left;
    private static int right;
    private static int[] nums;
    private static int diff = Integer.MAX_VALUE;
    private static int answer1 = 0;
    private static int answer2 = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        nums = new int[N];
        for (int i = 0; i < N; i++) {
            nums[i] = sc.nextInt();
        }
        left = 0;
        right = N - 1;
        Arrays.sort(nums); //정렬
        while (left < right) {
            int tmpDiff = Math.abs(nums[left] + nums[right]);  //두 수의 차이의 양수화
            if (tmpDiff < diff) { //0에 더 가까우면 정답 갱신
                diff = tmpDiff;
                answer1 = nums[left];
                answer2 = nums[right];
            }
            if (nums[left] + nums[right] > 0) { // 둘의 차이가 양수면 오른쪽 포인터를 더 작은 값을 가진
                // 왼쪽으로 움직음으로써 더 0에 가깝게 만들어본다.
                right--;
            } else {
                left++;
            }
        }
        System.out.println(answer1 + " " + answer2);
    }
}

 

 

 

댓글과 공감은 큰 힘이 됩니다. 감사합니다. !!