백준 : 3273번, 두 수의 합

문제 주소 : https://www.acmicpc.net/problem/3273

정답 비율 : 40.629% (2021.06.28 18:35 기준)

3273번: 두 수의 합

 

문제 조건 :

입력 : 수열의 크기 n이 주어지고 이어서 n개의 1 이상의 자연수(t)가 주어집니다. 마지막으로 x가 주어집니다. ( n : 1 ~ 100,000, t : 1 ~ 1,000,000, x : 1 ~ 2,000,000 )

출력 : 문제를 만족하는 쌍의 개수를 출력하면 됩니다.

시간 : 1초

 

문제 풀이 :

실제 계산이 이루어지는 범위를 보면  1 ~ 1,000,000으로 아주 큰 수가 아닌 것을 확인할 수 있습니다.

계수 정렬(Counting Sort) 기법을 사용하여 수의 유무만 알 수 있다면 arr[a] && arr[x - a]라는 조건으로 쉽게 만족하는 순서 쌍의 개수를 구할 수 있습니다.

 

코드는 다음과 같습니다.

// solve 3273
#include <stdio.h>

char arr[1000001];

int main(void) {
	int size = 0, sum = -1, ans = 0;

	scanf("%d", &size);

	for (int i = 0; i < size; i++) {
		int tmp = 0;
		scanf("%d", &tmp);
		arr[tmp] += 1;
	}
		
	scanf("%d", &sum);

	for (int i = 1; i < sum && i <= 1000000; i++) {
		if (sum - i <= 1000000) {
			if (arr[i]) {
				arr[i] -= 1;

				if (arr[sum - i]) {
					arr[sum - i] -= 1;
					ans++;
				}
			}
		}
	}

	printf("%d", ans);

	return 0;
}

-> arr[a] && arr[x - a]로 한 번에 하지 않고 따로 한 이유는 arr[2] = 1이고 x = 4인 경우에 arr[2] && arr[2]가 되므로 2는 한 개만 존재하는데 2개 있다고 취급을 하니 오류가 발생하게 됩니다.

 

*** 두 번째 풀이 ***

문제를 보면 2 SUM문제에서 단지 찾는 것에서 멈추는 것이 아니라 개수를 찾는 것만 바뀌었습니다. 따라서 해당 문제를 두 포인터 알고리즘을 사용하여서 푸는 것이 가능합니다.

 

흐름은 다음과 같습니다.

0. start = 0, end = n - 1 ans = 0으로 초기화합니다.

1. n개의 데이터를 오름 차순으로 정렬합니다.

2. arr[start] + arr[end]가 x와 같으면 ans와 start는 1을 증가하고 end는 1을 감소합니다.

3. arr[start] + arr[end]가 x보다 작으면 start는 1을 증가합니다.

4. arr[start] + arr[end]가 x보다 크면 end는 1을 감소합니다.

5. start >= end 될 때까지 2 ~ 4번을 반복합니다.

 

코드는 다음과 같습니다.

// solve 3273
#include <stdio.h>
#include <stdlib.h>

int arr[100000];

int compare(const void* a, const void* b) {
	return *(int*)a > * (int*)b ? 1 : -1;
}

int main(void) {
	int size = 0, sum = -1, ans = 0;
	int start = 0, end = 0;

	scanf("%d", &size);

	for (int i = 0; i < size; i++)
		scanf("%d", &arr[i]);

	scanf("%d", &sum);

	qsort(arr, size, sizeof(int), compare);

	end = size - 1;

	while (start < end) {
		if (arr[start] + arr[end] == sum) {
			ans++;
			start++;
			end--;
		}
		else if (arr[start] + arr[end] > sum) {
			end--;
		}
		else {
			start++;
		}
	}

	printf("%d", ans);

	return 0;
}