/ BOJ

BOJ_1141_접두사_JAVA

문제 : 접두사

링크 : BOJ_1141_접두사

접근 방식

특정 집합에서, 집합의 어떤 한 단어가 다른 단어의 접두어가 되지 않는 부분집합의 최대 크기를 구하는 문제이다.

먼저 집합을 문자열의 길이 순으로 오름차순 정렬을 하고, 뒤에서부터 거꾸로 가면서 접두어여부를 판단한다. 만약 접두어가 되는 경우에는 그 문자열을 ‘.’으로 바꾸어 탐색되지 않게 바꾸어주고, 카운팅했다. 최종적으로 .이 아닌 문자열의 개수가 집합의 최대 크기가 된다.

소스 코드

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

public class BOJ_1141_접두사2 {
	static char[][] chars;
	static int numbers[];
	static int N, R, ans = 1;

	public static void main(String[] args) throws IOException {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(in.readLine());

		chars = new char[N][];

		for (int i = 0; i < N; i++) {
			chars[i] = in.readLine().toCharArray();
		}

		Arrays.sort(chars, (char[] o1, char[] o2)->{
			return o1.length - o2.length;
		});

//		for(int i=0;i<N;i++) {
//			System.out.println(chars[i]);
//		}
		ans = N;
		for(int i=N-1;i>=0;i--) {

			for(int j=0;j<i;j++) {
				boolean check = false;
				for(int k=0;k<chars[j].length;k++) {
					if(chars[j][k] == '.' || chars[i][k] != chars[j][k]) {
						check = true;
					}
				}
				if(!check) {
					for(int k=0;k<chars[j].length;k++) {
						chars[j][k] = '.';
					}
					ans--;
				}

			}
		}


		System.out.println(ans);
	}



}