문제
N개의 문자열 집합에서 어떤 문자열도 다른 문자열의 접두사가 되지 않는 최대 부분집합의 크기를 구하라.
입력
첫째 줄에 N, 이후 N줄에 문자열이 주어진다.
출력
접두사 없는 최대 부분집합의 크기를 출력한다.
예제
| 입력 | 출력 |
|---|---|
5 hello hi h run rerun | 4 |
풀이
문자열을 길이 내림차순으로 정렬하고, 이미 선택된 문자열의 접두사가 아닌 것만 추가한다.
- 문자열을 길이가 긴 순으로 정렬한다
- 각 문자열에 대해, 이미 선택된 문자열 중 현재 문자열로 시작하는 것이 있는지 확인한다
- 접두사 관계가 없으면 리스트에 추가한다
- 최종 리스트의 크기가 답이다
핵심 아이디어: 긴 문자열부터 추가하면, 짧은 문자열이 긴 문자열의 접두사인 경우만 제외하면 된다.
코드
package day749;
import java.io.*;
import java.util.*;
public class Day722BOJ1141접두사 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
String[] arr = new String[N];
for (int i = 0; i < N; i++) {
arr[i] = br.readLine();
}
Arrays.sort(arr, (o1, o2) -> o2.length() - o1.length());
List<String> list = new ArrayList<>();
for (String cur : arr) {
if (list.size() == 0) {
list.add(cur);
continue;
}
boolean flag = false;
for (String str : list) {
if (str.indexOf(cur) == 0) {
flag = true;
break;
}
}
if (!flag) {
list.add(cur);
}
}
System.out.println(list.size());
}
}복잡도
- 시간: O(N² * L) - L은 최대 문자열 길이
- 공간: O(N * L)