[BaekJoon] 1141 접두사

1.  문제 링크

2.  문제

요약

• 접두X 집합은 집합의 어느 한 단어가 다른 단어의 접두어가 되지 않는 집합입니다.
• 단어 N개로 이루어진 집합에서 부분집합으로 접두사X 집합을 만들 때, 접두사X 집합의 최대 크기를 출력하는 문제입니다.
• 입력: 첫 번째 줄에 단어의 개수 N이 주어지고 두 번째 줄부터 N개의 줄에 단어가 주어집니다.
• 출력: 접두사X 집합의 최대 크기를 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;

public class Main {
	public int getPrefixSet(ArrayList<String> words) {
		for(int i = 0; i < words.size(); i++) {
			for(int j = 0; j < words.size(); j++) {
				if(i == j) {
					continue;
				}
				if(words.get(i).length() > words.get(j).length()) {
					if(words.get(i).indexOf(words.get(j)) == 0) {
						words.remove(j);
						if(i > j) {
							i--;
							j--;
						} else {
							j--;
						}
					}
				} else {
					if(words.get(j).indexOf(words.get(i)) == 0) {
						words.remove(i);
						i--;
						break;
					}
				}
			}
		}
		return words.size();
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int num = Integer.parseInt(br.readLine());
		ArrayList<String> words = new ArrayList<String>();
		for(int i = 0; i < num; i++) {
			words.add(br.readLine());
		}
        br.close();
		Main m = new Main();
        bw.write(m.getPrefixSet(words) + "\n");
		bw.flush();
        bw.close();
	}
}

4.  접근

• 주어진 단어들의 집합에서 첫 번째 단어부터 마지막 단어까지 다른 단어들의 접두사가 되는지를 확인하여 접두사가 되는 단어들을 제거한 후 남은 단어들의 개수가 접두사X 집합의 최대 크기가 됩니다.
• 전체 경우를 모두 확인하기 위해서 첫 단어부터 마지막 단어까지 전체 단어에 대해서 접두사가 되는지 확인합니다.
• 단어의 길이가 긴 단어에 길이가 짧은 단어가 접두사가 되는지 확인을 해야 하므로 현재 확인하려는 단어가 길이가 더 긴 경우와 대조해보려는 단어의 길이가 더 긴 경우로 나누어 진행합니다.
• 현재 확인하려는 단어가 길이가 더 긴 경우에는 만약 해당 단어가 접두사가 되는 경우, 대조해보려는 단어를 집합에서 제거하고 대조해보려는 단어의 길이가 더 긴 경우에는 확인해보려는 단어가 접두사가 되는 경우에는 확인해보려는 단어를 집합에서 제거합니다.
• 첫 단어부터 마지막 단어까지 위 방법을 이용하여 접두사가 되는 단어들을 제거하고 남은 단어들의 개수를 출력합니다.