[Baekjoon 1141] 접두사 - JAVA

[Silver I] 접두사 - 1141

문제 링크

성능 요약

메모리: 14344 KB, 시간: 128 ms

분류

그리디 알고리즘, 정렬, 문자열

문제 설명

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

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

입력

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

출력

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

문제 풀이

String으로 배열을 입력받아서 람다식을 이용하여 문자열의 길이로 정렬시켰다.
(람다식을 사용하지 않으면 사전순으로 정렬된다.)

이후, 각 문자열에 대해 비교를 통해 비접두사인 경우 nonPrefixStrings리스트에 따로 추가했다.

nonPrefixStrings 리스트의 크기를 출력하면 그게 곧 정답이 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.function.Function;

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());
        String[] strings = new String[N];

        for (int i = 0; i < N; i++) {
            strings[i] = br.readLine();
        }

        Arrays.sort(strings, (str1, str2) -> str2.length() - str1.length());
        List<String> nonPrefixStrings = new ArrayList<>();

        for (String currentString : strings) {
            if (nonPrefixStrings.size() == 0) {
                nonPrefixStrings.add(currentString);
                continue;
            }

            boolean isPrefix = false;

            for (String existingString : nonPrefixStrings) {
                if (existingString.indexOf(currentString) == 0) {
                    isPrefix = true;
                    break;
                }
            }

            if (!isPrefix) {
                nonPrefixStrings.add(currentString);
            }
        }

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

코드 풀이

        int N = Integer.parseInt(br.readLine());
        String[] strings = new String[N];

        for (int i = 0; i < N; i++) {
            strings[i] = br.readLine();
        }

• N: 단어의 개수를 입력받을 정수형 변수
• strings: 단어를 입력받을 문자열 변수

        Arrays.sort(strings, (str1, str2) -> str2.length() - str1.length());

• Arrays.sort()를 사용하여 strings 배열을 내림차순으로 정렬
• 람다식을 사용하여 정렬 기준은 문자열의 길이로, 길이가 긴 문자열이 앞으로 오도록 설정

        List<String> nonPrefixStrings = new ArrayList<>();

        for (String currentString : strings) {
            if (nonPrefixStrings.size() == 0) {
                nonPrefixStrings.add(currentString);
                continue;
            }

            boolean isPrefix = false;

            for (String existingString : nonPrefixStrings) {
                if (existingString.indexOf(currentString) == 0) {
                    isPrefix = true;
                    break;
                }
            }

            if (!isPrefix) {
                nonPrefixStrings.add(currentString);
            }
        }

• nonPrefixStrings: 비접두사(non-prefix) 문자열을 저장할 리스트
• strings 배열을 순회하며, 현재 문자열 currentString이 비접두사 리스트의 어떤 문자열의 접두사인지 검사한다.
• 만약 접두사가 아니라면, nonPrefixStrings 리스트에 해당 문자열을 추가한다.

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

• nonPrefixStrings 리스트의 크기를 출력하여 비접두사 문자열의 개수를 나타낸다.