어떤 문제인가?
개의 저장한 문자열과,개의 저장한 문자열을 비교해 그 개의 문자열 중 개의 문자열에 포함된 것이 얼마나 있는지 묻는 문제.
주의사항
총 N개의 문자열로 이루어진 집합 S가 주어진다.
입력으로 주어지는 M개의 문자열 중에서 집합 S에 포함되어 있는 것이 총 몇 개인지 구하는 프로그램을 작성하시오.
집합 원소 중에서 몇 개가 포함되는 것인지를 묻고 있고, 개의 문자열 중에서는 중복된 문자열이 포함될 수 있다.
시행착오 횟수
7번
구상들
1. 선형 탐색
2. Trie
3. Hash + Map
4. 단어 순 정렬 + 이분탐색
파이썬으로 풀면 머리 비우고 풀 수 있었는데, 구현 능력을 온전히 시험받기 위해서는 C99만큼 적당한 것도 없었다. 그래서 이 언어로 도전했다. 선형 탐색에서 실패한 후로는 2, 3번 중 무엇을 할까 고민했었는데, 해쉬 같은 경우에는 필자가 충돌이 안 나게 만들 자신이 없었다. 그래서 트라이로 선회했다.
사실 다른 사람들의 풀이를 보면 충돌이 나도 Chaining 기법으로 엮었다. 그냥 하면 됐었을 지도 모르겠는데, 트라이를 처음으로 구현했다는 것에 의미를 두려고 한다.
1차 시도: TE
char *S, T[501]={0};
int N,M,C=0;
scanf("%d", &N);
// trailing \0, 500 + 1.
S = (char *)calloc(N*501, sizeof(char));
scanf("%d", &M);
for(int i=0;i<N;i++)
scanf("%s", &S[i*501]);배열을 생성한 후 선형적으로 하나하나씩 비교하는 방식을 썼다. 이때 대충 가늠해보건대 이었고, 최악의 경우에는 번을 실행해야 했다. 실제로는 중간에 끝나는 경우가 많기에 이것보단 훨씬 작겠지만 어찌되었건 2초 내로 실행하기엔 어려워보였다.
그리고 당연히 시간 초과가 떴다.
2~4차 시도: RE
트라이로 선회한 후 몇가지 문제를 겪었다. 어디에서 문제가 생겼는지 짐작할 수 있겠는가?
#include <stdio.h>
#include <stdlib.h>
#define INDEX(a) ((int)a - (int)'a')
typedef struct Node {
struct Node* children[26];
int isEnd;
} Node;
Node* initNode() {
Node* node = (Node*)malloc(sizeof(Node));
node->isEnd = 0;
for(int i=0;i<26;i++)
node->children[i] = NULL;
return node;
}
int main() {
Node* root = initNode();
char T[51];
int N, M, c=0;
scanf("%d %d", &N, &M);
for(int i=0;i<N;i++) {
int j = 0;
Node* current = root;
scanf("%s", T);
while(T[j++] != '\0') {
if(!current->children[INDEX(T[j])])
current->children[INDEX(T[j])] = initNode();
current = current->children[INDEX(T[j])];
}
current->isEnd = 1;
}
for(int i=0;i<M;i++) {
int j = 0;
Node* current = root;
scanf("%s", T);
while(T[j++] != '\0') {
if(!current->children[INDEX(T[j])])
break;
current = current->children[INDEX(T[j])];
}
if(current->isEnd)
c++;
}
printf("%d", c);
return 0;
}- 멍청하게도
T[501]이 아니라T[51]로 잡았다. T[j++]로 써버리면\0문자까지INDEX()로 들어가게 되고, 그 함수는 음수를 반환한다. 따라서 OutOfBounds 오류가 뜨게 된다.
5차 시도: WA
런타임 오류가 뜰만한 것은 제거했는데, 이번에는 틀렸다고 한다. 슬슬 빡치기 시작한다.
#include <stdio.h>
#include <stdlib.h>
#define INDEX(a) ((int)a - (int)'a')
typedef struct Node {
struct Node* children[26];
int isEnd;
} Node;
Node* initNode() {
Node* node = (Node*)malloc(sizeof(Node));
node->isEnd = 0;
for(int i=0;i<26;i++)
node->children[i] = NULL;
return node;
}
int main() {
Node* root = initNode();
char T[501];
int N, M, c=0;
scanf("%d %d", &N, &M);
for(int i=0;i<N;i++) {
int j = 0;
Node* current = root;
scanf("%s", T);
while(T[j] != '\0') {
if(!current->children[INDEX(T[j])])
current->children[INDEX(T[j])] = initNode();
current = current->children[INDEX(T[j])];
j++;
}
current->isEnd = 1;
}
for(int i=0;i<M;i++) {
int j = 0;
Node* current = root;
scanf("%s", T);
while(T[j] != '\0') {
if(!current->children[INDEX(T[j])])
break;
current = current->children[INDEX(T[j])];
j++;
}
if(current->isEnd)
c++;
}
printf("%d", c);
return 0;
}6차 시도: WA
무엇이 잘못되었을 지 몇번이고 고민했는데, 이 때 개의 문자열 중 중복된 문자열이 있을 수 있다는 말을 보았다. 그래서 만약 이미 탐색한 것이라면 카운터를 올리지 못하도록 새로운 필드 변수 indexed 를 추가했다.
#include <stdio.h>
#include <stdlib.h>
#define INDEX(a) ((int)a - (int)'a')
typedef struct Node {
struct Node* children[26];
int isEnd;
int indexed;
} Node;
Node* initNode() {
Node* node = (Node*)malloc(sizeof(Node));
node->isEnd = 0;
node->indexed = 0;
for(int i=0;i<26;i++)
node->children[i] = NULL;
return node;
}
int main() {
Node* root = initNode();
char T[501];
int N, M, c=0;
scanf("%d %d", &N, &M);
for(int i=0;i<N;i++) {
int j = 0;
Node* current = root;
scanf("%s", T);
while(T[j] != '\0') {
if(!current->children[INDEX(T[j])])
current->children[INDEX(T[j])] = initNode();
current = current->children[INDEX(T[j])];
j++;
}
current->isEnd = 1;
}
for(int i=0;i<M;i++) {
int j = 0;
Node* current = root;
scanf("%s", T);
while(T[j] != '\0') {
if(!current->children[INDEX(T[j])])
break;
current = current->children[INDEX(T[j])];
j++;
}
if(current->isEnd && !current->indexed) {
current->indexed = 1;
c++;
}
}
printf("%d", c);
return 0;
}그러나 이 코드가 맞았습니다!를 받는 일은 없었다. 도대체 뭐가 문제일까?
7차 시도: AC
그렇다. 위 코드는 다음 테스트케이스를 통과하지 못한다.
4 4
b
bl
blu
blue
b
bttttt
bttttttt
bttttttttt
Expected: 1
Actual: 4왜일까? 바로 이 부분 때문이다.
if(!current->children[INDEX(T[j])])
break;이 부분에서 카운터를 올리지 않게끔 무언가 조치를 취했어야 했는데, 안 하고 넘기다 보니 위 테스트케이스에서 잘못된 결과를 내놓았던 것이다. 이 부분을 고치니 드디어 고대하던 맞았습니다! 를 받았다.
아래는 최종 코드이다.
#include <stdio.h>
#include <stdlib.h>
#define INDEX(a) ((int)a - (int)'a')
typedef struct Node {
struct Node* children[26];
int isEnd;
} Node;
Node* initNode() {
Node* node = (Node*)malloc(sizeof(Node));
node->isEnd = 0;
for(int i=0;i<26;i++)
node->children[i] = NULL;
return node;
}
int main() {
Node* root = initNode();
char T[501];
int N, M, c=0;
scanf("%d %d", &N, &M);
for(int i=0;i<N;i++) {
int j = 0;
Node* current = root;
scanf("%s", T);
while(T[j] != '\0') {
if(!current->children[INDEX(T[j])])
current->children[INDEX(T[j])] = initNode();
current = current->children[INDEX(T[j])];
j++;
}
current->isEnd = 1;
}
for(int i=0;i<M;i++) {
int j=0,n=0;
Node* current = root;
scanf("%s", T);
while(T[j] != '\0') {
if(!current->children[INDEX(T[j])]) {
n = 1;
break;
}
current = current->children[INDEX(T[j])];
j++;
}
if(current->isEnd && !n)
c++;
}
printf("%d", c);
return 0;
}다른 분들의 풀이
- 이분탐색 + 단어 순 정렬
# include <stdio.h>
# include <stdlib.h>
# include <string.h>
typedef struct
{
char str[501];
}dat;
dat arr[10000];
int main(void)
{
int N, M, i, cou=0;
char str[501];
scanf("%d%d", &N, &M);
for(i=0 ; i<N ; i++)
scanf("%s", arr[i].str);
qsort(arr, N, sizeof(dat), (int(*)(const void*, const void*))strcmp);
while(M--)
{
scanf("%s", str);
if(bsearch(str, arr, N, sizeof(dat), (int(*)(const void*, const void*))strcmp))cou++;
}
printf("%d", cou);
return 0;
}-> jaehoo님의 풀이
-> str[501]을 담는 구조체 선언을 한 후 strcmp로 비교하게 하는 건 생각도 못했다. 이게 되긴 하는구나. 게다가 이 방식이 메모리도 훨씬 적게 소모한다.
- 해쉬맵
다른 언어로 풀면 이 방식으로 쉽게 풀 수 있다. 그렇지만 C언어로 구현한 걸 어디에서 봤었는데, 정작 거기가 어디었는지는 기억이 나지 않는다. 아마도 구글에 치면 찾을 수 있을 것 같다.
