(JAVA) 백준 2470번 : 두 용액

https://www.acmicpc.net/problem/2470

2470번: 두 용액

 

 

그놈의 시간 초과 때문에 (제한시간 1초)

 

그리고 나만의 이진 탐색 방법을 사용하려고 하다보니

 

예외가 계속 나와서 그거 해결하느라 시간이 오래걸렸다.

 

 

결국에는

 

내 탐색 알고리즘으로 문제를 해결했으나..

*** 실제 이진탐색을 사용하는 방법도 있다.

 

베스트 정답을 보니 

 

이렇게 쉽게 풀 수 있는 방법이 있었어?

 

생각이 들며 

 

이 방법을 공부했다.

*** 정말 감사합니다.. 알고리즘 굇수님들..

 

 

그래서

 

필자가 처음에 구현한 알고리즘 이 아닌

 

베스트 효율적인 알고리즘을 포스팅하겠다.

 

 

 

핵심은 그렇다.

 

 

1) 음수, 양수가 섞인 배열을 우선 오름차순 정렬한다.

 

그렇게 되면 맨 왼쪽은 가장 낮은 음수, 맨 오른쪽은 가장 큰 양수가 자리하게 되고,

 

가운데로 갈수록 점점 절댓값은 작아질 것이다.

 

 

 

2) 그래서 양 끝부터 시작해서 탐색을 진행한다.

 

왼쪽 index를 i , 오른쪽 index를 j 라고 할 때

 

 

i ->    <- j

 

 

로 진행하며 i가 j보다 커지기 전까지 while문을 만족하는 반복문을 짠다.

 

 

3) 그래서 i의 원소와 j의 원소의 합(어떻게 말하면 두 원소 사이의 길이)의 절댓값을 저장하며

 

이전에 계산했던 절댓값보다 큰지 작은지 비교한다.

 

 

만약 이전 절댓값보다 작은 경우

 

정답에 가까워지기 때문에

 

이 두 원소를 별도 저장해두고, 위 절댓값을 이번에 계산해서 나온 절댓값으로 갱신한다.

 

 

이를 위 while문 조건을 벗어날 때 까지 반복한다.

 

 

 

 

그렇게해서 나온 결과가 정답이다.

 

?

 

그렇게해서 나온 별도로 저장한 두 원소가

 

모든 원소들 중 임의로 선택한 두 원소의 차가 0에 가장 가까운 두 원소라는 뜻이다!

 

 

 

간단한 문제를...

 

아직 부족하다고 느낀다.

 

 

 

 

소스코드를 하단에 첨부하겠습니다.

 

오늘도 항상 웃는 하루가 되었으면 좋겠습니다.

 

감사합니다! :)

 

 

소스코드

---

	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	import java.util.ArrayList;
	import java.util.Arrays;
	import java.util.StringTokenizer;
	// 두 용액
	// 이진탐색 비슷한 문제
	public class p2470 {
	public static void main(String[] args) throws NumberFormatException, IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	int n = Integer.parseInt(br.readLine());
	int[] arr = new int[n];
	StringTokenizer st = new StringTokenizer(br.readLine());
	for (int i = 0; i < n; i++) {
	arr[i] = Integer.parseInt(st.nextToken());
	}
	Arrays.sort(arr);
	int i = 0;
	int j = arr.length - 1;
	int gap = Integer.MAX_VALUE;
	int ans1 = 0;
	int ans2 = 0;
	int temp;
	int sum;
	while (i < j) {
	sum = arr[i] + arr[j];
	temp = Math.abs(sum);
	if (temp < gap) {
	gap = temp;
	ans1 = arr[i];
	ans2 = arr[j];
	}
	if (sum > 0)
	j--;
	else
	i++;
	}
	System.out.println(ans1 + " " + ans2);
	}
	}

view raw p2470.java hosted with ❤ by GitHub