[백준] 1141번: 접두사(JAVA)

▶ 문제

https://www.acmicpc.net/problem/1141

1141번: 접두사

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

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

입력

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

출력

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

---

▶ 풀이

 - JAVA

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

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

        Collections.sort(li, 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(li.get(j).startsWith(li.get(i))){
                    ans--;
                    break;
                }
            }
        }

        System.out.println(ans);
    }
}

---

▶ 메모

boolean startsWith(String prefix): 대상 문자열이 특정 문자 또는 문자열로 시작하는지 확인하는 함수

boolean endsWith(String prefix): 대상 문자열이 특정 문자 또는 문자열로 끝나는지 확인하는 함수

String str = "Test";

System.out.println(str.startsWith("Te")); // true
System.out.println(str.startsWith("te")); // false (대소문자 비교 O)
System.out.println(str.endsWith("st")); // true
System.out.println(str.endsWith("sT")); // false (대소문자 비교 O)

 

 

Array, ArrayList 는 Comparator 을 이용하여 정렬할 수 있다.

class NumberComparator implements Comparator<Number> {
    @Override
    public int compare(Number number1, Number number2) {
        return number1.getValue() - number2.getValue();		//오름차순
        //return number2.getValue() - number1.getValue();	//내림차순
    }
}