글 읽기 - 트라이로 풀 때,

gudrkrsla 4년 전 0

모든 문자열을 다 받은 다음 하나하나 insert 해주는 식으로 풀이해서 맞았습니다.

그래서 반복을 조금이라도 줄이고자, 문자열을 받으면서 그 즉시 insert해주는 식으로 바꾸었는데 틀렸습니다를 받았습니다.

뭐가 문제일까요?? 첨부코드는 틀렸을 때 코드입니다.

#include<stdio.h>
int t,n;
struct Trie{
	Trie *next[10];
	bool finish;
	void insert(const char *key){
		if(*key=='\0')finish=true;
		else{
			int Index=*key-'0';
			if(next[Index]==NULL)
				next[Index]=new Trie();
			next[Index]->insert(key+1);
		}
	}
	
	bool find(const char *key){
		if(*key=='\0')return false;
		if(finish)return true;
		int Index=*key-'0';
		return next[Index]->find(key+1);
	}
};

typedef Trie Trie;
int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		char Number[10001][10];
		int flag = 0;
        Trie *root = new Trie();
		for(int i=0;i<n;i++){
            scanf("%s",Number[i]);
            root->insert(Number[i]);
        }
		for(int i=0;i<n;i++)
			if(root->find(Number[i])){
				flag=1;
				break;
			}
		if(flag)printf("NO\n");
		else printf("YES\n");
	}	
}

djm03178 4년 전 1

new로 할당된 메모리는 초기화가 되지 않습니다. next와 finish 모두에 어떤 값이 들어있을지 전혀 모르는 상태가 됩니다.

gudrkrsla 4년 전 0

답변 감사드립니다. 초기화 관련해서, Trie에 생성자, 소멸자를 추가시켜주고, test_case 종료마다 root를 delete 시켜주는 식으로 수정해보았는데, 여전히 통과가 되질 않네요ㅠㅠ

#include<stdio.h>
#include<iostream>
using namespace std;
int t,n;


struct Trie{
	Trie *next[10];
	bool finish;
	
	Trie() :finish(false){
        for (int i=0;i<10;i++)
            next[i] = 0;
    }
    ~Trie(){
        for (int i=0;i<10;i++)
            if (next[i]) delete next[i];
    }
	void insert(const char *key){
		if(*key=='\0')finish=true;
		else{
			int Index=*key-'0';
			if(next[Index]==NULL)
				next[Index]=new Trie();
			next[Index]->insert(key+1);
		}
	}
	
	bool find(const char *key){
		if(*key=='\0')return false;
		if(finish)return true;
		int Index=*key-'0';
		return next[Index]->find(key+1);
	}
};
typedef Trie Trie;

int main(){
	cin>>t;
	while(t--){
		cin>>n;
		char Number[10001][10];
		int flag = 0;
        Trie *root = new Trie();
		 for (int i=0;i<n;i++){
            cin >> Number[i];
            root->insert(Number[i]);
        }
      	
		for(int i=0;i<n;i++)
			if(root->find(Number[i])){
				flag=1;
				break;
			}
			
		if(flag)printf("NO\n");
		else printf("YES\n");
        delete root;
	}	
}

djm03178 4년 전 2

전화번호의 길이가 최대 10자리이므로 Number 배열의 1차원의 크기는 널 문자까지 담기 위해 최소 11칸이 되어야 합니다. 그것만 고치니 맞았습니다.

gudrkrsla 4년 전 0

아...감사합니다..아주 간단한 기초를 놓지고 있었군요..

마지막으로, 처음에 acc 받은 코든데, 이게 왜 통과가 되는지를 잘 모르겠는데, 좀 알 수 있을까요??

#include<stdio.h>
int t,n;
struct Trie{
	Trie *next[10];
	bool finish;
	void insert(const char *key){
		if(*key=='\0')finish=true;
		else{
			int Index=*key-'0';
			if(next[Index]==NULL)
				next[Index]=new Trie();
			next[Index]->insert(key+1);
		}
	}
	
	bool find(const char *key){
		if(*key=='\0')return false;
		if(finish)return true;
		int Index=*key-'0';
		return next[Index]->find(key+1);
	}
};
typedef Trie Trie;
int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		char Number[10001][10];
		for(int i=0;i<n;i++)
           scanf("%s",Number[i]);
      	int flag = 0;
        Trie *root = new Trie();
        for(int i=0;i<n;i++)
        	root->insert(Number[i]);
		for(int i=0;i<n;i++)
			if(root->find(Number[i])){
				flag=1;
				break;
			}
		if(flag)printf("NO\n");
		else printf("YES\n");
	}	
}

djm03178 4년 전 2

Number[i][10]은 Number[i+1][0]의 주소와 같아지는데, 그러면 i+1번째에 삽입된 문자열은 i번째 문자열의 널 문자를 덮어쓰게 됩니다. 그러면 i번째 문자열을 삽입/검색할 때는 마치 i번째 문자열의 뒤에 i+1번째 문자열을 이어붙인 걸 삽입/검색하는 것과 같아지는데, 이걸로 틀리게 만들 수 있는 반례가 없는 것 같습니다.

틀렸습니다를 받은 코드의 경우에는 삽입할 때의 문자열은 10글자에서 딱 끊어진 상태로 들어가는데 검색할 때는 더 긴 문자열을 찾으려고 하는 것처럼 되어 검색 과정에서 잘못된 동작을 일으키기 때문인 것 같습니다.

djm03178 4년 전 2

답이 틀리지는 않은데, 메모리 초과가 날 수 있는 데이터를 만들었습니다.

https://www.acmicpc.net/board/view/44326

gudrkrsla 4년 전 1

와...정말 감사합니다..ㅠㅠ테스트 케이스에서 오류를 잡아낼 반례가 없는 것이었군요....

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

트라이로 풀 때,

gudrkrsla 4년 전 0

djm03178 4년 전 1

gudrkrsla 4년 전 0

djm03178 4년 전 2

gudrkrsla 4년 전 0

djm03178 4년 전 2

djm03178 4년 전 2

gudrkrsla 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말