백준 접두사

문제

내가 생각했을때 문제에서 원하는부분

첫째 줄에 단어의 개수 N이 주어진다.
N은 50보다 작거나 같은 자연수이다.
둘째 줄부터 N개의 줄에는 단어가 주어진다.
단어는 알파벳 소문자로만 이루어져 있고,
길이는 최대 50이다.
집합에는 같은 단어가 두 번 이상 있을 수 있다.

첫째 줄에 문제의 정답을 출력한다.

내가 이 문제를 보고 생각해본 부분

BufferedReader를 사용하여 단어의 개수 (N)을 입력받고,
그 다음 (N)개의 단어를 리스트에 추가한다.
list는 주어진 단어들을 저장하는 역할이다.
Collections.sort를 통해 리스트의 단어들을 길이 기준으로 오름차순 정렬한다.
짧은 단어가 먼저 나오도록 하여,
접두사 관계를 쉽게 확인할 수 있게 한다.
짧은 단어가 긴 단어의 접두사가 될 수 있기 때문에,
이렇게 정렬하는 것이 중요하다.
두 개의 반복문을 사용하여 각 단어 (i)와 그 뒤의 단어 (j)를 비교한다.
list.get(j).startsWith(list.get(i))를 통해 (j)번째 단어가 (i)번째 단어의 접두사인지 확인한다.
만약 (j)번째 단어가 (i)번째 단어의 접두사라면,
(ans)를 감소시키고, 더 이상 (j)를 확인할 필요가 없으므로 내부 반복문을 종료한다.
이는 접두사X 집합의 조건을 만족하기 위해 필요하다.
최종적으로 접두사X 집합의 크기를 출력한다.
(ans)는 접두사 관계가 성립하지 않는 단어의 개수를 말한다.

코드로 구현

package baekjoon.baekjoon_24;

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

// 백준 1141번 문제
public class Main847 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        List<String> list = new ArrayList<>();
        for(int i = 0; i < N; i++)
            list.add(br.readLine());

        Collections.sort(list, new Comparator<String>(){
            public int compare(String s1, String s2){
                return s1.length() - s2.length();
            }
        });

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

        System.out.println(ans);
        br.close();
    }
}

마무리

코드와 설명이 부족할수 있습니다. 코드를 보시고 문제가 있거나 코드 개선이 필요한 부분이 있다면 댓글로 말해주시면 감사한 마음으로 참고해 코드를 수정 하겠습니다.