문제
김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. 이름은 띄어쓰기 없이 영어 소문자로만 이루어지며, 그 길이는 20 이하이다. N, M은 500,000 이하의 자연수이다.
출력
듣보잡의 수와 그 명단을 사전순으로 출력한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
|
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<stdbool.h>
#pragma warning(disable:4996)
#pragma warning(disable:6031)
char A[500000][22]; //듣도 못한 사람
char B[22]; //보도 못한 사람
char C[500000][22]; //듣도 보도 못한 사람
bool BinarySearch(char name[], int num) { //이분 탐색(찾는 문자열,배열 크기)
int start = 0;
int end = num - 1;
int mid = (start + end) / 2;
while (start <= end) {
mid = (start + end) / 2;
if (strcmp(A[mid], name) == 0)return true; //찾으면 1 반환
else if (strcmp(A[mid], name) < 0)start = mid + 1; //key가 더 나중이면 뒷부분 탐색
else end = mid - 1; //key가 더 먼저면 앞부분 탐색
}
return false; //못 찾으면 0 반환
}
int main() {
int n, m, count = 0;
scanf("%d%d", &n, &m); //n,m 입력
getchar();
for (int i = 0; i < n; i++) {
fgets(A[i], 22, stdin); //듣도 못한 사람 입력
}
qsort(A, n, sizeof(A[0]), strcmp); //듣도 못한 사람 정렬
for (int i = 0; i < m; i++) {
fgets(B, 22, stdin); //보도 못한 사람 입력
if (BinarySearch(B, n) == 1) { //만약 듣도 못한 사람에도 있으면
strcpy(C[count++], B); //듣도 보도 못한 사람에 복사
}
}
qsort(C, count, sizeof(C[0]), strcmp); //듣도 보도 못한 사람 정렬
printf("%d\n", count); //듣도 보도 못한 사람 수
for (int i = 0; i < count; i++) {
printf("%s", C[i]); //듣도 보도 못한 사람 출력
}
return 0;
}
|
cs |
A에 듣도 못한 사람의 이름을 저장해준다.
이름을 입력받을 때마다 이분탐색을 실행해서 만약 A에 있는 사람이면 C에 복사해준다.
strcmp 의 반환값은 -1, 0, 1 이 아니라는 것을 주의하면 될 것 같다.
'백준 온라인 저지 (BOJ) 문제풀이' 카테고리의 다른 글
백준 온라인 저지 (BOJ) 18422 Emacs (0) | 2020.09.23 |
---|---|
백준 온라인 저지 (BOJ) 10819 차이를 최대로 (0) | 2020.09.23 |
백준 온라인 저지 (BOJ) 10773 제로 (0) | 2020.09.23 |
백준 온라인 저지 (BOJ) 1463 1로 만들기 (0) | 2020.09.22 |
백준 온라인 저지 (BOJ) 15989 1,2,3 더하기 4 (0) | 2020.09.21 |