[백준] 1141 접두사 - 문자열(String) + 해시셋(HashSet) + 정렬(Sort) + Comparator JAVA

https://www.acmicpc.net/problem/1141

코드설명

문자열(String) + 해시셋(HashSet) + 정렬(Sort) 을 활용합니다.

 

접두사로 포함되지 않게 하기 위해

1. 길이에 따라 내림차순 정렬을 합니다.

2. 각 문자를 substr(0, 끝위치) (여기서 끝위치는 포함안되고 endIndex - 1 까지가 포함, 즉 [0, endIndex - 1] ) 로 Hashset에 삽입합니다.

3. 중복확인으로 접두사 X인 단어들만 선별하여 삽입합니다.

 

구현시에 유의할 사항은 Comparator입니다.

저는 Arrays.sort에 익명함수 Comparator를 직접 구현해서 사용했습니다.

Arrays.sort(words, 0, N, new Comparator<String>() {
    @Override
    public int compare(String word1, String word2) {
        return Integer.compare(word2.length(), word1.length());
    }
});

 

당연히, 아래와 같이 익명함수 대신 Class를 따로 만들어서 하는것도 가능합니다.

Arrays.sort(words, 0, N, new WordLengthComparator());
        
class WordLengthComparator implements Comparator<String>{
	@Override
	public int compare(String word1, String word2) {
		return Integer.compare(word2.length(), word1.length());
	}
}

 

코드

package Main;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashSet;
import java.util.StringTokenizer;
 
public class Main {
	static int N, M, S, P, K, A, B, X, L, R;
	static int answer = 0;
	static HashSet<String> hashset = new HashSet<>();
	static String[] words = new String[51];
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			words[i]= st.nextToken();
		}
		Arrays.sort(words, 0, N, new Comparator<String>() {
			@Override
			public int compare(String word1, String word2) {
				return Integer.compare(word2.length(), word1.length());
			}
		});
		
		for(int i=0; i<N; i++) {
			if(hashset.contains(words[i]) == false) {
				answer += 1;
				for(int j=0; j<=words[i].length(); j++) {
					hashset.add(words[i].substring(0,j));
				}
			}
		}
		System.out.println(answer);
	}
}