[BOJ] 1141 접두사 - JAVA

1. 문제

1141번: 접두사

접두사X 집합이란 집합의 어떤 한 단어가, 다른 단어의 접두어가 되지 않는 집합이다. 예를 들어, {hello}, {hello, goodbye, giant, hi}, 비어있는 집합은 모두 접두사X 집합이다. 하지만, {hello, hell}, {giant, gig, g}는 접두사X 집합이 아니다.

단어 N개로 이루어진 집합이 주어질 때, 접두사X 집합인 부분집합의 최대 크기를 출력하시오.

---

2. 풀이

1.  입력 문자열을 전부 리스트에 넣고 정렬한다.

2.  하나씩 탐색하면서 j문자열이 i 문자열로 시작한다면 리스트에서 i문자열을 지우고 i-1을 한 뒤 다시 탐색한다.

import java.io.*;
import java.util.*;

public class BOJ_1141_접두사 {
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      int N = Integer.parseInt(in.readLine());
      ArrayList<String> list = new ArrayList<>(N);
      for(int i=0;i<N;i++) list.add(in.readLine());

      Collections.sort(list);

      for(int i=0;i<list.size();i++){
         for(int j=i+1;j<list.size();j++){
            if(list.get(j).startsWith(list.get(i))) {
               list.remove(i);
               i--;
               break;
            }
         }
      }

      System.out.println(list.size());
   }
}

---

3. 결과