[백준/1141/접두사/실버1]

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

1141번: 접두사

 

<<풀이>>

 

시간복잡도 : O(N^3)

 

사용한 방법 : Comparable<T> 정렬

 

->

우선, 이 문제는 Comparable<T>로 객체를 정렬시킨 뒤에 풀어야 하는 문제이다. 그렇게 해야 문제를 조금 더 쉽게 접근이 가능하다.

 

그런데, 이상하게 이 문제가 틀렸다... 예시 코드는 다 맞느데 말이다..

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

class Data implements Comparable<Data>{
    String data= "";
    int datalength = data.length();

    public Data(String data, int datalength) {
        this.data = data;
        this.datalength = datalength;
    }


    @Override
    public int compareTo(Data o) {

        return this.datalength - o.datalength;
    }
}

class Main {
    static int answer2 = 0;

    private int solution(Data[] brr) {
        int answer = 0;
        for (int i = 0; i < brr.length - 1; i++) {
            answer = 0;
            int count = 0;
            for (int j = i; j < brr.length; j++) {
                if (brr[j].data.indexOf(brr[i].data) != 0 ) {
                    for (int k = j; k < brr.length; k++) {
                        if(brr[k].datalength != brr[j].datalength && brr[k].data.indexOf(brr[j].data) == 0) {
                            count--;
                        }
                    }
                    count++;
                }

            }
            answer = count + 1;
            answer2 = Math.max(answer2, answer);
        }
        return answer2;
    }



    public static void main(String[] args) throws Exception{
        Main T = new Main();
        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++) {
            String a = br.readLine();
            arr[i] = a;
        }

        Data[] brr = new Data[n];

        for (int i = 0; i < n; i++) {
            brr[i] = new Data(arr[i], arr[i].length());
        }

        Arrays.sort(brr);
        System.out.println(T.solution(brr));

    }
}

 

 

<<최종 풀이>>

이 문제는 사전순으로 정렬을 하고 푸는 것이 가장 효과적인 방법이었다..!!

 

그렇게 하면 이전꺼와만 비교해도 되는 것이다.

 

사전 순으로 해서 현재 것이 이전 것과 조합이 안 되고, 그 다음 과도 조합이 안 된다면 당연히 이전 값과 그 다음 값 과도 조합이 안 된다.

이런 생각으로 접근을 한다면 쉽게 접근이 가능하다.

 

이건 글로만 보는 것 보다 직접 써보면서 논리구조를 파악하는 것이 훨씬 좋다.

 

indexOf 보다 훨씬 좋은 좋은 메서드를 발견했다. 바로 startWith인 셈이다. 이를 활용하면 굳이

 

indexOf가 값이 0인가에 대해 비교할 필요가 없다 ㅋㅋㅋ

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

class Data implements Comparable<Data> {
    String data;

    public Data(String data) {
        this.data = data;
    }

    @Override
    public int compareTo(Data o) {
        // 사전순으로 정렬
        return this.data.compareTo(o.data);
    }
}

class Main {
    private int solution(Data[] brr) {
        // 사전순으로 정렬
        Arrays.sort(brr);

        int count = 1; // 최소 하나의 단어는 항상 포함됩니다.
        for (int i = 0; i < brr.length - 1; i++) {
            // 현재 단어가 다음 단어의 접두사인지 확인
            if (!brr[i + 1].data.startsWith(brr[i].data)) {
                // 접두사가 아니면 부분집합에 포함할 수 있습니다.
                count++;
            }
        }
        return count;
    }

    public static void main(String[] args) throws Exception {
        Main T = new Main();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        Data[] brr = new Data[n];

        for (int i = 0; i < n; i++) {
            String data = br.readLine();
            brr[i] = new Data(data);
        }

        System.out.println(T.solution(brr));
    }
}

 

 

<<추가 공부>>

 

startsWtih : 첫 시작의 문자열이 특정 값인가?

 

indexOf : 특정 문자가 몇 번 인덱스부터 있는가?

 

객체 정렬

Comparable<T>

 

1. 사전순

 @Override
    public int compareTo(Data o) {
        // 사전순으로 정렬
        return this.data.compareTo(o.data);
    }

 

2. 오름차순

 

 @Override
    public int compareTo(Data o) {

        return this.datalength - o.datalength;
    }

 

3. 내림차순

 

 @Override
    public int compareTo(Data o) {

        return o.datalength - this.datalength;
    }