시아98
174
2021-03-17 19:44:30
0
147

백준 5670번(트라이알고리즘) 혹시 도와주실 수 있으신 분 계신가요?


5670문제

백준 5670문제를 풀고 있는데 값도 정상적으로 나오고 제 눈에는 잘 작동하는 것 같은데 어디가 틀렸는지 도저히 안보이네요... 혹시 도와주실 수 있으신 분 계신가요? 트라이 알고리즘을 사용했습니다.



import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n;
		String input = new String();
		ArrayList <String> word = new ArrayList<>(); 
		trie T = new trie();
		int sum=0;
		double avg;
		
		n = sc.nextInt();
		for(int i=0; i<n; i++) // 단어 입력과 노드 추가
		{
			input = sc.next();
			word.add(input);
			T.insert(input);
		} 
		
		for(int i=0; i<n; i++) // 각 입력 횟수의 합을 구하기 
			sum += T.find( T, word.get(i) );
		
		avg = (double)sum / (double)n;
		System.out.format("%.2f%n", avg);
		
	}
}

class trie_Node 
{
	Map<Character, trie_Node> chd_Node = new HashMap<>();
	boolean last_check = false;	
}

class trie
{
	trie_Node root = new trie_Node();
	
	void insert(String input)
	{
		trie_Node temp = this.root;
		
		for(int i=0; i<input.length(); i++)
		{
			if( temp.chd_Node.get( input.charAt(i)) == null )
			{
				temp.chd_Node.put( input.charAt(i), new trie_Node() );
				temp = temp.chd_Node.get( input.charAt(i) );
			}
			else
				temp = temp.chd_Node.get( input.charAt(i) );
		}
		temp.last_check = true;
	}
	
	
	int find(trie T, String input)
	{
		int count = 1;
		trie_Node temp = T.root.chd_Node.get( input.charAt(0) ); // 먼저 1번 입력했다고 가정하고 시작합니다.
		
		for(int i=1; i<input.length(); i++)
		{
			if(temp.chd_Node.size() >= 2)
				count++;
			
			else if( temp.chd_Node.size() == 1 && temp.last_check == true )
			{
				count++;
			}
			
			temp = temp.chd_Node.get( input.charAt(i) );
			
		}
		
		
		return count;
	}
}



0
  • 답변 0

  • 로그인을 하시면 답변을 등록할 수 있습니다.