백준 2470 두 용액

백준 2470←클릭

투 포인터를 사용하는 문제이다. 배열을 오름차순으로 정렬하여 투 포인터를 사용하면 쉽게 풀린다.

변수 설정

arr: 전체 배열
left: 왼쪽 포인터
right: 오른쪽 포인터
left_ans: 작은 정답값
right_ans: 큰 정답값

투 포인터 구현

• 배열을 오름차순으로 정렬한다.
  
  
• 배열의 가장 왼쪽 인덱스와 오른쪽 인덱스를 left와 right에 저장한다.
  
  
• 포인터가 가리키는 두 값을 더한다.
  
  
• 더한 값의 절대값이 기존 minimum보다 작으면 minimum값을 교체
  
  
• 더한 값이 0보다 클 경우 right를 하나 줄인다. 0보다 작을 경우 left를 하나 키운다.
  
  
• 더한 값이 0이 나오거나 right가 left보다 왼쪽에 있게되면 종료한다.

코드

github

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
using namespace std;

int main() {
	//freopen("input/2470_input.txt", "r", stdin);
	int N, minimum = 2000000000;
	int arr[100001];
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}
	sort(arr, arr+N);
	int left = 0, right = N - 1, val = arr[left] + arr[right];
	int left_ans = arr[left], right_ans = arr[right];
	while (left < right) {
		val = arr[left] + arr[right];
		if (abs(minimum) > abs(val)) {
			minimum = val;
			left_ans = arr[left];
			right_ans = arr[right];
		}
		if (val == 0)break;
		else if (val > 0) right--;
		else left++;
	}
	cout << left_ans << " " << right_ans << endl;
	
}

느낀점

시험도 끝났으니까 코딩 공부 다시 해야겠다...!

정답~.~