https://www.acmicpc.net/problem/1269
C
#include <stdio.h>
#include <stdlib.h>
int compare(const void* a, const void* b)
{
int num1 = *(int*)a;
int num2 = *(int*)b;
if (num1 < num2) return -1;
else if (num1 > num2) return 1;
else return 0;
}
int binarySearch(int start, int end, int find, int arr[])
{
int mid;
while (start <= end)
{
mid = (start + end) / 2;
if (find == arr[mid]) return 1;
else if (find < arr[mid]) end = mid - 1;
else if (find > arr[mid]) start = mid + 1;
}
return 0;
}
int main()
{
int a, b, result=0;
scanf("%d %d", &a, &b);
int* arrA = (int*)malloc(sizeof(int) * a);
int* arrB = (int*)malloc(sizeof(int) * b);
for (int i = 0; i < a; i++) scanf("%d", &arrA[i]);
for (int i = 0; i < b; i++) scanf("%d", &arrB[i]);
qsort(arrA, a, sizeof(int), compare);
qsort(arrB, b, sizeof(int), compare);
for (int i = 0; i < a; i++) result += binarySearch(0, b - 1, arrA[i], arrB);
for (int i = 0; i<b; i++) result += binarySearch(0, a - 1, arrB[i], arrA);
printf("%d", a + b - result);
free(arrA);
free(arrB);
return 0;
}
C++
#include <iostream>
#include <cstdlib>
using namespace std;
int compare(const void* a, const void* b)
{
int num1 = *(int*)a;
int num2 = *(int*)b;
if (num1 < num2) return -1;
else if (num1 > num2) return 1;
else return 0;
}
int binarySearch(int start, int end, int find, int arr[])
{
int mid;
while (start <= end)
{
mid = (start + end) / 2;
if (find == arr[mid]) return 1;
else if (find < arr[mid]) end = mid - 1;
else if (find > arr[mid]) start = mid + 1;
}
return 0;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int a, b, result = 0;
cin >> a >> b;
int* arrA = new int[a];
int* arrB = new int[b];
for (int i = 0; i < a; i++) cin >> arrA[i];
for (int i = 0; i < b; i++) cin >> arrB[i];
qsort(arrA, a, sizeof(int), compare);
qsort(arrB, b, sizeof(int), compare);
for (int i = 0; i < a; i++) result += binarySearch(0, b - 1, arrA[i], arrB);
for (int i = 0; i < b; i++) result += binarySearch(0, a - 1, arrB[i], arrA);
cout << a + b - result;
delete []arrA;
delete[]arrB;
return 0;
코드설명
메인 함수
동적배열로 집합을 만들고, 각각 반복문을 돌면서 값들을 입력받는다.
qsort 함수로 배열을 오름차순으로 정렬한다.
반복문을 돌면서 binarySearch함수에서 반환하는 값을 결과에 더해나간다.
반환하는 값이 0이면 마지막 인수로 받은 배열에만 존재하는 값이라는 뜻이고, 1이면 양쪽 배열 모두에 존재하는 값이라는 뜻이다.
두 배열의 요소의 합에서 중복되어 있는 값이 있으므로 result을 빼서 출력한다.
binarySearch 함수
시작 인덱스와 끝 인덱스, 찾는 값, 배열을 인수로 받는다.
배열은 정렬되어 있으므로 중간값이 찾는 값이라면 바로 1을 반환한다.
중간값이 찾는 값보다 크다면 중간값 뒤쪽에 있는 숫자들은 비교할 필요가 없다. 그러므로 끝 인덱스를 중간값-1로 한다.
중간값이 찾는 값보다 작다면 중간값 앞쪽의 숫자들은 비교할 필요가 없으므로 시작 인덱스를 중간값+1로 한다.
만약 값을 끝까지 찾지 못했다면 0을 반환한다.
느낀 점
처음에 문제를 보고 아무 생각 없이 이중for문을 사용해서 문제를 풀었는데, (당연히) 시간 초과가 되었다.
그래서 구글에서 다른 분들이 푼 방식을 봤는데, 이 글을 보고 방향을 제대로 잡았다. (https://www.crocus.co.kr/633)
그래서 나는 qsort를 써서 집합들을 정렬한 후 이진탐색을 써서 문제를 풀었다.
'PS (C, C++)' 카테고리의 다른 글
[백준/C & C++] 2740 행렬 곱셈 (0) | 2023.01.29 |
---|---|
[백준/C & C++] 1124 언더프라임 (0) | 2023.01.28 |
[백준/C & C++] 1764 듣보잡 (0) | 2023.01.26 |
[백준/C & C++] 2477 참외밭 (0) | 2023.01.25 |
[백준/C & C++] 21921 블로그 (0) | 2023.01.24 |