[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
- 장점: 다양한 입력 소스를 처리할 수 있고, 여러 유형의 입력을 읽을 수 있음.
- 단점: 상대적으로 무겁고, 입력 소스가 커질 경우 성능이 떨어질 수 있음.
이와 같이, 각 클래스와 메서드에는 장단점이 있으며, 사용 목적과 상황에 맞춰 선택하는 것이 중요합니다.
'여러가지 > 알고리즘 & 자료구조' 카테고리의 다른 글
[백준] 나이트의 이동 - 7562번 (1) | 2024.06.10 |
---|---|
[백준] 열 개씩 끊어 출력하기 - 11721번 (0) | 2024.06.01 |
동적 프로그래밍과 반대 개념 프로그래밍 (1) | 2024.05.31 |
[백준] 피보나치 수1 - 24416번 (0) | 2024.05.31 |
[백준]알고리즘의 수행 시간 6 - 24267 (0) | 2024.05.31 |