c언어 7423번 디스크 트리 (백준)

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

typedef struct Trie {
    char data[9]; //단어의 길이는 1~8까지다. (널문자 공간 1 비어놓아야 한다)
    struct Trie * next;
    struct Trie * child;
}Trie;

Trie * insert(Trie * root, char str[]) {
    Trie * newNode = malloc(sizeof(Trie));
    newNode->next = NULL;
    newNode->child = NULL;
    strcpy(newNode->data, str);
    
    Trie * p = root->child;
    Trie * bp = NULL; // before p
    
    if(p!=NULL) {
        //exist?
        for(;p!=NULL;p=p->next) {
            int tmp = strcmp(str, p->data);
            if(tmp == 0) {
                free(newNode);
                return p;
            }
             else if(tmp < 0) {
                //non exist, and it's small
                if(bp == NULL) root->child = newNode;
                else bp->next = newNode; //bp -> p     bp->newNode->p
                newNode->next = p;
                return newNode;
            }
            bp = p;
        }
        //non exist, and it's most big
        bp->next = newNode;
        return newNode; 
        
    } else {
        root->child = newNode; 
        return newNode; 
    } return NULL;
}

void find(Trie*root, int depth) {
    for(Trie * p = root->child; p!=NULL; p=p->next) {
        for(int i=0; i<depth; i++) printf(" ");
        printf("%s\n",p->data);
        find(p, depth+1);
    }
}

int main()
{
    int n;
    char str[81]={};
    Trie * root = (Trie*) malloc(sizeof(Trie));
    root->next = NULL;
    root->child = NULL;
    
    scanf("%d",&n);
    for(int i=0; i<n; i++) {
    	scanf("%s",str);
    	
        Trie * tmp = root;
        int start = 0;
        for(int j=0; ; ++j) {
        	if(str[j] == '\\') { //특수 문자이므로 \\ 앞에 \ 을 붙여야 한다
        		str[j] = '\0';
        		tmp = insert(tmp, str+start);
        		start = j+1; //offset
			} else if(str[j] == '\0') { //입력받은 문자열이 끝났다.
				tmp = insert(tmp, str+start);
				break;
			}
		}
    }
    
    find(root, 0);
    
    return 0;
}

 

풀이 : 트라이

 

https://h202.tistory.com/776

c언어 14725번 개미굴 (백준)

위의 문제와 풀이방법은 거의 같습니다.

 

다른점은 문자열을 입력받은 부분입니다.

 

14725번에선 공백을 기준으로 단어를 띄어서 줬지만

 

여기선 \ 이걸로 분리해서 주고 있습니다.

 

고로 %s로 한 문자열로 입력을 받은 다음

 

for문을 이용하여 \이 나오는 부분을 \0으로 바꾸고 트라이에 집어 넣고

 

또 \이 나오면 그 부분을 \0으로 바꿔서 트라이에 넣고

 

마지막으로 \0 이 나오면 본래 입력받은 문자열이 끝났음을 의미하고 반복문을 종료합니다.

 

여기서 중요한 점은 str 에 offset을 더해주어야 합니다.

str 자체는 주소값이기 때문에 \ 이 나왔던 부분의 index에 +1을 하면 이것이 offset이 되며

이것을 str에 더해주면 \ 다음 문자부터 시작하는 주소값이 됩니다.

 

이해가 안된다면 아래 그림을 보면 됩니다.

 

이렇게 하면 굳이 변수를 하나 또 만들어서, \나 \0기 전까지 문자들을 복사할 필요가 없습니다. 그냥 주소값에 offset만 더해주면 됩니다!!!!

 

여기서 \을 왜 \0으로 바꿔야 하는지 의문이 들수도 있습니다만,
c언어에선 문자열을 다룰 때 시작주소만 줄 뿐, 끝은 \0으로 판단하기 때문에, 원하는 단어를 다루기 위해선 꼭 \을 \0으로 바꾸어 주어야 합니다.

 

\0은 널문자 입니다. 값은 0 입니다.

 

Trie 부분은 개미굴 문제 풀이에 나와 있습니다.