[C++] 백준 3273번 - 두 수의 합

www.acmicpc.net/problem/3273

3273번: 두 수의 합

1보다 크거나 같고, 1000000보다 작거나 같은 n개의 서로 다른 양의 정수 수열을 받아 자연수 x가 주어졌을 때 두 수의 합이 x가 되는 수열 안의 쌍의 개수를 구하는 문제입니다.

 

문제를 푼 지가 조금 오래되어서 처음에 구현하였던 코드는 정확히 생각이 잘 나지 않는데, 처음에는 입력을 배열에 저장하고 합을 확인하기 위해 배열을 이중으로 돌며 더한 값이 x가 되는지 확인하고 count를 1씩 증가시키는 방법을 사용하였습니다.

 

하지만 위와 같이 구현했을 때 이미 카운트된 수인 것을 확인해야 하고, 반복을 이중으로 하여 시간이 오래 걸리기 때문에 배열을 한 번만 돌며 확인하는 방법으로 구현합니다.

O(n)의 시간복잡도로 입력 배열을 한 번만 돌면서 count를 증가시키기 위해 이미 확인했다는 것을 검사하기 위한 배열을 추가로 선언, 검사를 하지 않았던 수라면 tmp배열 값을 1로 변경합니다.

 

#include<iostream>
using namespace std;

int tmp[1000001];
int arr[100001];

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

	int n, x;
	int count = 0;
	cin >> n;

	for (int i = 0; i < n; i++)
	{
		cin >> arr[i];
	}
	cin >> x;

	for (int i = 0; i < n; i++)
	{
		if (tmp[x - arr[i]] == 1)
			count++;
		else
			tmp[arr[i]] = 1;
	}

	cout << count;

	return 0;
}

 

배열에 관한 알고리즘 게시글은 여기에서 확인하실 수 있습니다.