백준 1141 - 접두사 ( JAVA )

출처 - 백준 알고리즘

1141번: 접두사

---

[ 알고리즘 ] 

 정렬 + HashSet 

 

• 정렬 : A 단어가 B 단어의 접두어가 되기 위해서는 [  'A의 길이' <= 'B 의 길이' ] 여야 한다. ( ex ) h <= hi )  길이가 긴 문자열부터 탐색하며 , 다음 문자열들을 접두어로 포함하는지 아닌지 판단한다. → 길이순 내림차순 정렬 
• HashSet : 집합에 중복되는 단어가 주어질 수 있기 때문에 Set을 활용하여 중복을 제거한다. 

 

 

1. 주어진 문자열의 집합을 내림차순으로 정렬한다. 

 

2. 정렬된 문자열 집합을 순서대로 탐색하며 아래 조건에 따라 Set에 삽입한다. 

   ( 현재 탐색하고 있는 문자열을 A 라고 가정 , ) 

   - Set이 비어있을 경우, A를 add. (= 첫번째 원소)

 

   - Set이 비어있지 않을 경우, 

• A를 제일 앞쪽에 포함하고 있는 문자열이 존재할 경우, set 에 넣지 않는다. ( = 접두어 ) 
• 존재하지 않을 경우, set에 add 

 

3. set 의 크기 ( set.size() ) 

 

 

 String.indexOf(a) : 문자열에서 'a'가 나오기 시작하는 인덱스를 반환 

  ex ) String s= "hello" 일때, s.indexOf("e") = 1 

---

[ 코드 ] 

import java.util.*;
import java.io.*;

public class Solution_BaekJoon_1141 {
	public static void main(String[] args) throws Exception{
		Set<String> set = new HashSet<String>(); 
		
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in)); 
		
		int N= Integer.parseInt(br.readLine()); // 단어의 갯수 
		String[] words = new String[N];
		
		for(int i=0; i<N; i++) {
			words[i] = br.readLine();
		}
		
		// 길이순으로 정렬
		Arrays.sort(words, (o1,o2)->{
			return o2.length() - o1.length();
		});
		
		// SET 이기 때문에 중복된 문자열은 들어가지 X 
		for(int i=0; i<N; i++) {
			String word= words[i];
			
			if(set.size() ==0 ) {
				set.add(word);
				continue; 
			}
			// 해당 문자열을 set 에 넣을 수 있는지 여부 
			boolean flag= true;
			// 해당 문자열을 접두어로 가지는 문자열이 있을 경우, 
			for(String s : set) {
				if(s.indexOf(word) == 0) {
					flag= false;
					break; 
				}
			}
			
			if(flag) set.add(word); 
		}
	
		System.out.println(set.size());
		
	}//end of main 
}//end of class

끗 !