문제 링크 : https://www.acmicpc.net/problem/2470


합이 0에 가장 가까운 두 용액을 구하는 문제입니다.


N이 최대 100,000 인데 시간제한 1초인데다가 언어별 추가시간이 없기 때문에 O(n)으로 풀어야 합니다.


비효율적으로 푸는 방법은 N개중에서 2개를 뽑는 콤비네이션을 완전탐색으로 돌려서 푸는 방법이 있긴 합니다.


O(N)에 푸는 방법은 우선 배열을 정렬합니다.


그다음 가장 가장 작은 숫자인 arr[0]과 가장 큰 숫자인 arr[n-1]을 더한 후에 max 값과 비교합니다.


만약에 두 숫자의 합이 0보다 크다면 arr[n-1]의 절대값이 arr[0]보다 더 크기때문에 arr[n-1]의 인덱스를 하나 줄여줍니다.


반대로 두 숫자의 합이 0보다 작다면 arr[0]의 인덱스를 하나 증가시킵니다.


이렇게 배열의 양쪽 끝에서부터 서로 줄여가면서 합이 0에 가장 가까운 숫자를 구하면 됩니다.


import java.util.*;
import java.io.*;
// https://www.acmicpc.net/problem/2470
class Main {
static int stoi(String s) {
return Integer.parseInt(s);
}
static int pick1 = -1;
static int pick2 = -1;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int n = stoi(br.readLine());
int[] arr = new int[n];
st = new StringTokenizer(br.readLine());
for(int i=0; i<n; i++)
arr[i] = stoi(st.nextToken());
Arrays.sort(arr);
solution(n, arr);
System.out.println(pick1 + " " + pick2);
}
static void solution(int n, int[] arr) {
int left = 0;
int right = n-1;
int max = 2000000000;
while(left < right) {
int sum = arr[left] + arr[right];
// 두 용액 갱신
if(Math.abs(sum) < max) {
pick1 = arr[left];
pick2 = arr[right];
max = Math.abs(sum);
}
if(sum > 0)
right--;
else
left++;
}
}
}
view raw BOJ2470.java hosted with ❤ by GitHub

+ Recent posts