[210315][백준/BOJ] 3273번 두 수의 합

문제

입출력

---

풀이

단순하게 O(n^2)으로 풀었다가 시간초과가 발생하였다.
다시 문제를 읽어보니 배열의 크기가 최대 10만이다. n이 1000이상일 경우에는 O(n^2)을 사용할시 시간초과가 발생한다.
따라서 이진탐색( O(logN) )으로 풀어야 하는 문제이다.

1. 이진탐색으로 문제를 풀기 위해서 일단 배열이 정렬되어 있어야한다.
   따라서 sort 함수를 사용하여 오름차순으로 정렬하였다.

2. 다음으로는 left와 right값을 설정해야 한다.
   left, right 초기값을 각각 0과 n-1로 설정한 다음에 탐색을 시작한다.
   또한 left값이 right값보다 작을동안 반복문이 실행된다.

3. 1) 두 수의 합(arr[left] + arr[right])이 x와 같다면
   cnt를 증가시키고 다음 탐색을 하기 위해서 left값을 1 증가시키고 right값을 1 감소시킨다.
   2) 두 수의 합이 x보다 크다면 합이 더 작아져야 하므로 right 값을 1 감소시킨다.
   3) 두 수의 합이 x보다 작다면 합이 더 커져야 하므로 left 값을 1 증가시킨다.

코드

#include <bits/stdc++.h>
using namespace std;

int arr[100001];

int main(void)
{
	int n, x, cnt = 0;
	scanf("%d", &n);
	
	for (int i = 0; i < n; ++i)
		scanf("%d", &arr[i]);
	scanf("%d", &x);

	sort(arr, arr + n);
	int left = 0, right = n - 1;

	while (left < right)
	{
		if (arr[left] + arr[right] == x)
		{
			cnt++;
			left++;
			right--;
		}
		else if (arr[left] + arr[right] > x)
			right--;
		else
			left++;
	}
	printf("%d", cnt);
}

---

느낀점

문제의 조건들을 잘 읽어보고 풀어야할거 같다.
내간 구현한 코드의 시간복잡도를 잘 생각해보고 이 코드가 시간제한안에 돌아갈지 생각하면서 문제를 풀어야겠다.