아이디어

• 문자열을 사전 순으로 정렬하면 어떤 단어의 접두사는 반드시 그 단어보다 위에 있게 된다.
• 사전 순으로 정렬 후 역순으로 탐색하며 그 단어를 부분집합에 포함시킬 지 아닐지를 본다.
• 현재 부분집합에 있는 어떤 단어에도 접두사가 되지 않으면 포함시키면 된다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tk = null;
	
	static int N, ans;
	static String[] words;
	static boolean[] contained;

	public static void main(String[] args) throws Exception {
		N = Integer.parseInt(rd.readLine());
		
		words = new String[N];
		contained = new boolean[N];
		for (int i=0; i<N; i++) {
			words[i] = rd.readLine();
		}
		
		Arrays.sort(words);

		for (int i=N-1; i>=0; i--) {
			boolean ok = true;
			for (int j=i+1; j<N; j++) {
				if (contained[j] && words[j].startsWith(words[i])) {
					ok = false;
					break;
				}
			}
			if (ok) {
				contained[i] = true;
				ans++;
			}
		}
		
		System.out.println(ans);
	}
}

메모리 및 시간

• 메모리: 14244 KB
• 시간: 132 ms

리뷰

• 역순이 아니라 순서대로 탐색하는 방식으로 하려고 별 짓을 다했던 문제...