[백준] 2470-두 용액(C++)

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

2470번: 두 용액

 

투포인터 알고리즘을 사용한 문제였습니다.

 

접근방식

 

1. 일반적인 방식으로 모든값을 비교해준다면 o(N^2)로 시간초과

2. 양쪽에 포인터를 생성하고 필요한 만큼씩만 비교하며 진행하기로 함

 

 

 

 

문제풀이 

 

1. 왼쪽부터 오른쪽으로 진행

2. 왼쪽의 절대값이 오른쪽 절대값보다 클경우 더 비교할 필요가 없으니 break

 ex) -10 2 3 5 에서 -10 + 5가 0번 인덱스에선 최선

3.  두값이 같은경우에는 비교할 수 없기 때문에 break

4. 그 외에 right값이 감소해야 하는 경우에는 right--

 

 

아래는 정답코드입니다. 예외처리를 할 케이스들이 많은 문제였습니다. 화이팅

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

int n;
int arr[100001] = { 0, };
int index = 0;
int result = 2000000000;
int r1, r2;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
		if (arr[i] < 0)
			index++;
	}
	sort(arr, arr + n);
	//cout << index << endl;
	if (index == 0) {
		cout << arr[0]<< ' '<< arr[1] << endl;
		return 0;
	}
	if (index == n) {
		cout << arr[n - 2]<< ' '<< arr[n - 1] << endl;
		return 0;
	}

	
	int right = n - 1;

	for (int i = 0; i < n; i++) { // 모든 수를 검사 
		while (1) {
			if (i < right &&  abs(arr[i] + arr[right]) < result) { // ex) -999 -998 1
				result = abs(arr[i] + arr[right]);
				r1 = arr[i], r2 = arr[right];
			}

			if (abs(arr[i]) > abs(arr[right]))
				break;
			if (right == index)
				break;
			right--;
		}
	}


	cout << r1 << ' ' << r2 << endl;

	return 0;
}