백준1141 - 문자열, 그리디

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

1141번: 접두사

 

난이도: SILVER 1

 

java로 알고리즘을 푸는 것을 도전중이다.

static main에 대해 모든 걸 static 으로 구현하는 점, input,output이 다른 점 등이 색다르다. 

 

이번 문제는 접두사 부분집합의 최대개수를 다루는 문제이다.

해당 접두사들은 대표 접두사만 저장하고, 해당 접두사를 포함하는 문자열이라면 그냥 지나가는게 핵심이다.

또한, 접두사는 다른 포함하는 문자열에 대해 가장 문자열의 길이가 작으므로, 문자열 길이 순으로 정렬한 뒤 

접두사 포함여부를 따지면서 포함하면 된다. 

 

 

- 알아가는 java 문법: string.indexOf(String str) -> str를 포함한다면 시작되는 인덱스 값. 없다면 -1 값을 리턴

https://docs.oracle.com/javase/8/docs/api/java/lang/String.html

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader bfn = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(bfn.readLine());
        String[] inputs = new String[n];

        for(int i = 0 ; i < n; i++){
            String input = bfn.readLine();
            inputs[i] = input;
        }

        
        ArrayList<String>wordGroup =  new ArrayList();
        
        //문자열의 길이 순으로 정렬
        //짧은 순서대로 확인하면서 접두사 여부를 확인한다. 
        Arrays.sort(inputs, (str1, str2) -> str2.length() - str1.length());
    
        for(String input : inputs) {
        //처음
        if (wordGroup.size() == 0){
            wordGroup.add(input);
            continue;
        }

        boolean isNewWord = true;

        for(String existingString : wordGroup){
            if(existingString.indexOf(input) == 0){
                isNewWord = false;
                break;
            }
        }
        if(isNewWord == true)
            wordGroup.add(input);
        
    }
        System.out.print(wordGroup.size());
    }
    


}