[C] 백준 3273번: 두 수의 합

 문제에 탐색, 정렬 알고리즘을 바로바로 적용시키는 연습을 한창 하고있다. 안한지 꽤 오래돼서 파악하는데 좀 걸린다. 이번 문제 역시 문제는 쉽지만 제한시간을 맞춰야하기 때문에 정렬과 탐색을 적절히 사용해야 한다. 나는 시간복잡도 O(n * log n)으로 했다.

입출력 예시

정답코드

#include <stdio.h>
#include <stdlib.h>

void quickSort(int *, int, int);
int inPlacePartition(int *, int, int, int);
int search(int *, int, int);

int main() {

	int n;
	int x;

	int *arr;
	int i;

	int tmp;
	int count = 0;

	scanf("%d", &n);

	arr = (int *)malloc(sizeof(int) * n);

	for (i = 0; i < n; i++) {
		scanf("%d", arr + i);
	}

	scanf("%d", &x);

	quickSort(arr, 0, n - 1);

	for (i = 0; i < n; i++) {
		tmp = search(arr, n - 1, x - arr[i]);

		if (tmp != -1) {
			if (arr[i] < tmp) {
				count++;
			}
		}
	}

	printf("%d", count);

	return 0;

}

void quickSort(int *arr, int l, int r) {

	int a, b;

	if (l >= r) return;

	a = b = inPlacePartition(arr, l, r, r);

	quickSort(arr, l, a - 1);
	quickSort(arr, b + 1, r);

}

int inPlacePartition(int *arr, int l, int r, int k) {

	int p = arr[k];
	int tmp;

	int i, j;

	p = arr[k];

	tmp = arr[k];
	arr[k] = arr[r];
	arr[r] = tmp;

	i = l;
	j = r - 1;

	while (i <= j) {
		while (i <= j && arr[i] <= p) {
			i++;
		}
		while (j >= i && arr[j] >= p) {
			j--;
		}
		if (i < j) {
			tmp = arr[i];
			arr[i] = arr[j];
			arr[j] = tmp;
		}
	}

	tmp = arr[i];
	arr[i] = arr[r];
	arr[r] = tmp;

	return i;

}

int search(int *arr, int n, int x) {

	int l = 0;
	int r = n;

	int m;

	while (l <= r) {

		m = (l + r) / 2;

		if (x == arr[m]) return arr[m];

		if (arr[m] < x) l = m + 1;
		else if (arr[m] > x) r = m - 1;

	}

	return -1;

}

코드설명

1. n을 입력받고, arr에 n개의 int 배열을 동적할당 해주고 n개의 int 값을 입력받는다. x를 입력받는다.

2. 배열 arr을 quickSort 해준다. 기준 원소는 항상 제일 끝에 있는 원소로 한다. 여기서 기대 실행시간은 O(n * log n)

3. 배열 arr의 각 원소를 기준으로 x를 만드는 데 필요한 값을 이진탐색을 이용해 찾는다. 단, 기준원소보다 찾은 값이 큰 경우에만 갯수를 추가한다. 여기서 실행시간 O(n)