[백준] 3273번 두수의 합

www.acmicpc.net/problem/3273

3273번: 두 수의 합

처음에 짰던 코드는

입력을 배열에 저장 후 2중 for문을 통해 O(N^2)으로 원소를 2개씩 조합하여 확인하는 것이었다.

 

검색을 통해 O(N)으로 처리한 방식이 인상적이였어서 개인적으로 남겨놓고 싶다.

 

1. 입력을 배열에 저장후 sort를 통해 배열을 오름차순으로 정리한다.

2. 2개의 커서를 배열의 시작값과 끝값에 존재시키고 반복문을 실행한다.

3. 2개의 커서가 가르키는 갚들의 합을 tmp에 저장시킨다.

4. tmp의 값에 따라 result(결과값)을 증가시키거나 시작커서를 증가시키거나 끝커서를 종료시키는 과정을 수행한다.

5. 시작 커서의 값이 끝 커서보다 같거나 커지면 반복문을 종료시킨다.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int n, x, cnt;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int n, x;
	vector<int> arr;
	int result = 0;

	cin >> n;

	int buf;
	for (int i = 0; i < n; i++) {
		cin >> buf;
		arr.push_back(buf);
	}

	cin >> x;

	int start = 0;
	int end = n - 1;

	sort(arr.begin(), arr.end());

	while (end > start) {
		buf = arr[start] + arr[end];
		if (buf == x) {
			result++;
			start++;
			end--;
		}

		else if (buf > x)
			end--;

		else start++;
	}

	cout << result;
}