[백준] KMP는 왜 KMP일까? - 2902번

[Bronze II] KMP는 왜 KMP일까? - 2902

문제 링크

느낀점

다른 풀이 중 StringTokenizer를 보았으며 아주 유용하다는 사실을 알게 되었다.

StringTokenizer st = new StringTokenizer(br.readLine(), "-")
int tokenSize = st.countTokens();

while(st.has

성능 요약

메모리: 14188 KB, 시간: 104 ms

분류

구현, 문자열

제출 일자

2024년 5월 31일 23:38:37

문제 설명

KMP 알고리즘이 KMP인 이유는 이를 만든 사람의 성이 Knuth, Morris, Prett이기 때문이다. 이렇게 알고리즘에는 발견한 사람의 성을 따서 이름을 붙이는 경우가 많다.

또 다른 예로, 유명한 비대칭 암호화 알고리즘 RSA는 이를 만든 사람의 이름이 Rivest, Shamir, Adleman이다.

사람들은 이렇게 사람 성이 들어간 알고리즘을 두 가지 형태로 부른다.

• 첫 번째는 성을 모두 쓰고, 이를 하이픈(-)으로 이어 붙인 것이다. 예를 들면, Knuth-Morris-Pratt이다. 이것을 긴 형태라고 부른다.
• 두 번째로 짧은 형태는 만든 사람의 성의 첫 글자만 따서 부르는 것이다. 예를 들면, KMP이다.

동혁이는 매일매일 자신이 한 일을 모두 메모장에 적어놓는다. 잠을 자기 전에, 오늘 하루 무엇을 했는지 되새겨 보는 것으로 하루를 마감한다.

하루는 이 메모를 보던 중, 지금까지 긴 형태와 짧은 형태를 섞어서 적어 놓은 것을 발견했다.

이렇게 긴 형태로 하루 일을 기록하다가는 메모장 가격이 부담되어 파산될 것이 뻔하기 때문에, 앞으로는 짧은 형태로 기록하려고 한다.

긴 형태의 알고리즘 이름이 주어졌을 때, 이를 짧은 형태로 바꾸어 출력하는 프로그램을 작성하시오.

입력

입력은 한 줄로 이루어져 있고, 최대 100글자의 영어 알파벳 대문자, 소문자, 그리고 하이픈 ('-', 아스키코드 45)로만 이루어져 있다. 첫 번째 글자는 항상 대문자이다. 그리고, 하이픈 뒤에는 반드시 대문자이다. 그 외의 모든 문자는 모두 소문자이다.

출력

첫 줄에 짧은 형태 이름을 출력한다.

코드

package KMP는왜KMP일까;

import java.io.*;


public class Main { 
    public static void main(String[] args) throws IOException {

        /**
         * 
         * 문자열 처리 (String Manipulation)
         *
         * 1. split 메소드를 사용하여 문자열을 특정 구분자로 분리
         * 2. charAt 메소드를 사용하여 문자열에서 특정 인덱스의 문자를 추출
         *3.  StringBuilder를 사용하여 문자열을 효율적으로 조합
         * 
         */
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); // BufferedWriter를 사용하여 표준 출력(System.out)에 씁니다.

        String[] wordArr = br.readLine().split("-"); // 입력된 문자열을 '-'로 나누어 배열에 저장합니다.
        int N = wordArr.length;                             // 배열의 길이를 변수 N에 저장합니다.

        StringBuilder sb = new StringBuilder();
        for(int i=0;i<N;i++){
            sb.append(wordArr[i].charAt(0)); // 각 요소의 첫 번째 문자를 StringBuilder에 추가합니다.
        }

        bw.write(sb.toString());
        bw.flush();
        br.close();
        bw.close();
    }
}

StringTokenizer 사용법 및 예시

StringTokenizer는 Java에서 문자열을 구분자를 기준으로 분리하는 데 사용되는 클래스입니다. 이 클래스는 레거시 클래스이지만 여전히 많이 사용됩니다. 사용법은 다음과 같습니다:

 

1 생성자

• StringTokenizer(String str): 문자열 str을 공백을 기준으로 분리합니다.
• StringTokenizer(String str, String delim): 문자열 str을 지정된 구분자 delim을 기준으로 분리합니다.
• StringTokenizer(String str, String delim, boolean returnDelims): 구분자를 토큰으로 간주할지 여부를 지정합니다.

2 주요 메서드

• boolean hasMoreTokens(): 더 많은 토큰이 있는지 확인합니다.
• String nextToken(): 다음 토큰을 반환합니다.
• int countTokens(): 남아있는 토큰의 수를 반환합니다.

코드 예시

주어진 코드에서 StringTokenizer를 사용하여 문자열을 구분자로 분리한 후, 각 부분 문자열의 첫 글자를 추출합니다.

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

public class Main2 {
    public static void main(String[] args) throws IOException {
        String input = "Knowlege-Man-Power";
        String DELIMETER = "-";
        BufferedReader br = new BufferedReader(new StringReader(input));
        StringTokenizer st = new StringTokenizer(br.readLine(), DELIMETER);
        StringBuilder sb = new StringBuilder();

        while (st.hasMoreTokens()) {
            sb.append(st.nextToken().charAt(0));
        }
        System.out.println(sb.toString());
    }
}

대체 클래스 및 메소드

StringTokenizer는 과거부터 사용되어 왔지만, 최근에는 더 간편하고 기능적인 클래스들이 많이 나왔습니다. 특히 String.split() 메서드와 Scanner 클래스가 많이 사용됩니다.

 

1 String.split()

• split(String regex): 정규 표현식을 사용하여 문자열을 분리합니다.
• split(String regex, int limit): 정규 표현식을 사용하여 문자열을 분리하며, 분리할 최대 횟수를 지정할 수 있습니다.

2 Scanner 클래스

• Scanner(String source): 문자열을 입력 소스로 사용합니다.
• useDelimiter(String pattern): 스캐너에서 사용할 구분자를 지정합니다.
• hasNext(), next(): 다음 토큰이 있는지 확인하고, 토큰을 반환합니다.

String.split()을 사용한 대체 코드

import java.io.*;

public class Main2 {
    public static void main(String[] args) throws IOException {
        String input = "Knowlege-Man-Power";
        String DELIMETER = "-";
        BufferedReader br = new BufferedReader(new StringReader(input));
        String[] tokens = br.readLine().split(DELIMETER);
        StringBuilder sb = new StringBuilder();

        for (String token : tokens) {
            sb.append(token.charAt(0));
        }
        System.out.println(sb.toString());
    }
}

Scanner를 사용한 대체 코드

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

public class Main2 {
    public static void main(String[] args) throws IOException {
        String input = "Knowlege-Man-Power";
        String DELIMETER = "-";
        BufferedReader br = new BufferedReader(new StringReader(input));
        Scanner scanner = new Scanner(br.readLine());
        scanner.useDelimiter(DELIMETER);
        StringBuilder sb = new StringBuilder();

        while (scanner.hasNext()) {
            sb.append(scanner.next().charAt(0));
        }
        System.out.println(sb.toString());
        scanner.close();
    }
}

비교

 

1 StringTokenizer

• 장점: 간단하고 직관적인 사용법.
• 단점: 구분자를 여러 개 사용할 수 없고, 유연성이 떨어짐.

2 String.split()

• 장점: 정규 표현식을 사용하여 구분자를 지정할 수 있어 매우 유연함.
• 단점: 정규 표현식을 이해해야 함.

3 Scanner

• 장점: 다양한 입력 소스를 처리할 수 있고, 여러 유형의 입력을 읽을 수 있음.
• 단점: 상대적으로 무겁고, 입력 소스가 커질 경우 성능이 떨어질 수 있음.

이와 같이, 각 클래스와 메서드에는 장단점이 있으며, 사용 목적과 상황에 맞춰 선택하는 것이 중요합니다.