문제
내가 생각했을때 문제에서 원하는부분
첫 번째 줄에는 알파벳 소문자, 대문자, 숫자로 이루어진 문자열 S가 주어진다. (1 ≤ |S| ≤ 200,000)
두 번째 줄에는 성민이가 찾고자 하는 알파벳 소문자, 대문자로만 이루어진 키워드 문자열 K가 주어진다. (1 ≤ |K| ≤ 200,000)
단, 입력으로 들어오는 키워드 문자열 K의 길이는, 교과서의 문자열 S보다 짧거나 같다.
첫 번째 줄에 성민이가 찾고자 하는 키워드가 교과서 내에 존재하면 1, 존재하지 않으면 0을 출력한다.내가 이 문제를 보고 생각해본 부분
main 메서드: 프로그램의 시작점
사용자로부터 원본 문자열 S (알파벳 + 숫자)와 찾고자 하는 키워드 K (알파벳만)를 입력받는다.
kmpSearchWithDigitSkip 함수를 호출하여 S 내에서 K를 검색하고, 결과에 따라 1(찾음) 또는 0(못 찾음)을 출력한다.
입출력 효율을 위해 BufferedReader를 사용하며, 사용 후에는 반드시 닫아준다.
getPi 메서드: 패턴 K를 위한 점프 테이블 생성
이 함수는 키워드 K를 분석하여 pi 배열(부분 일치 테이블)을 만든다.
pi[i] 값은 K의 0부터 i까지의 부분 문자열에서 '가장 긴 접두사이자 동시에 접미사가 되는 부분의 길이'를 저장한다.
이 pi 배열은 KMP 검색 중 패턴이 텍스트와 불일치했을 때, 패턴을 얼마나 효율적으로 이동시켜야 할지 알려주는 중요한 역할을 한다.
패턴 K 자체에는 숫자가 없으므로 이 로직은 표준 KMP의 pi 테이블 생성 방식과 동일하다.
kmpSearchWithDigitSkip 메서드: 숫자를 건너뛰는 최적화된 KMP 검색
이 함수가 S에서 K를 찾는 핵심 로직이며, "시간 초과"를 해결하기 위한 최적화가 적용되어 있다.
초기화: S의 길이 n, K의 길이 m을 저장하고, K에 대한 pi 배열을 가져온다.
j는 패턴 K의 현재 일치 길이를 나타내는 인덱스이다.
S 문자열 순회 (for 루프): S의 각 문자를 i 인덱스로 순서대로 검사한다.
숫자 건너뛰기 (if (Character.isDigit(textS.charAt(i))) { continue; }):
S의 현재 문자 textS.charAt(i)가 숫자인지 확인한다.
만약 숫자라면, 키워드 K는 알파벳으로만 구성되므로 이 숫자는 K와 일치할 수 없다.
따라서 이 문자는 무시하고 continue를 통해 S의 다음 문자로 바로 넘어간다.
이때 패턴 인덱스 j는 변경되지 않는다.
이것이 새로운 문자열을 만들지 않고 효율적으로 숫자를 처리하는 핵심 부분이다.
KMP 불일치 처리 (while 루프):
S의 현재 문자가 숫자가 아니고, K의 j번째 문자와 일치하지 않을 때, pi 배열을 참조하여 j 값을 조정한다.
이는 KMP 알고리즘의 표준 동작으로, 불필요한 비교를 건너뛰어 탐색 효율을 높이다.
KMP 일치 처리 (if 문):
S의 현재 문자가 숫자가 아니고, K의 j번째 문자와 일치하는 경우이다.
j == m - 1 이라면: K의 모든 문자가 S의 (숫자를 제외한) 부분과 성공적으로 일치한 것이다.
true를 반환하고 검색을 종료한다.
그렇지 않다면 (j가 K의 끝이 아니라면): j를 1 증가시켜 패턴의 다음 문자와의 비교를 준비한다.
결과 반환: S 전체를 다 탐색했지만 K를 찾지 못했다면 false를 반환한다.코드로 구현
package baekjoon.baekjoon_30;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
// 백준 16172번 문제
public class Main1150 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 첫 번째 줄: 알파벳, 숫자 포함된 문자열 S 읽기
String S = br.readLine();
// 두 번째 줄: 알파벳으로만 이루어진 키워드 K 읽기
String K = br.readLine();
// KMP 알고리즘으로 S(원래 문자열)에서 K를 검색
// 숫자를 미리 제거하는 과정 없이 KMPSearch 내에서 숫자를 건너뛰도록 구현
if(kmpSearchWithDigitSkip(S, K)) {
System.out.println(1); // 찾으면 1 출력
} else {
System.out.println(0); // 못 찾으면 0 출력
}
br.close();
}
// 패턴의 pi 배열(부분 일치 테이블) 계산 함수 (이전과 동일)
public static int[] getPi(String pattern) {
int m = pattern.length();
int[] pi = new int[m];
int j = 0;
for(int i = 1; i < m; i++) {
while(j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
j = pi[j - 1];
}
if(pattern.charAt(i) == pattern.charAt(j)) {
j++;
}
pi[i] = j;
}
return pi;
}
// 숫자를 건너뛰면서 KMP 검색을 수행하는 함수
public static boolean kmpSearchWithDigitSkip(String textS, String patternK) {
int n = textS.length(); // 텍스트(S)의 길이
int m = patternK.length(); // 패턴(K)의 길이
// 패턴의 pi 배열(부분 일치 테이블) 계산 (K는 숫자 포함 안 함)
int[] pi = getPi(patternK);
// 텍스트를 탐색하며 패턴 매칭
int j = 0; // 패턴(K)의 현재 인덱스
for(int i = 0; i < n; i++) { // 텍스트(S)의 현재 인덱스
// S[i]가 숫자인 경우, 이 문자는 무시하고 S의 다음 문자로 넘어감
if(Character.isDigit(textS.charAt(i))) {
continue; // j는 유지된 채 i만 증가
}
// 불일치 발생 시, pi 배열을 이용해 j를 적절히 이동 (패턴의 인덱스를 재조정)
// 단, K는 숫자가 없으므로 S[i]는 항상 알파벳임
while(j > 0 && textS.charAt(i) != patternK.charAt(j)) {
j = pi[j - 1];
}
// 일치하는 경우, j 증가
if(textS.charAt(i) == patternK.charAt(j)) {
// 패턴의 끝까지 일치했는지 확인
if(j == m - 1) {
return true; // 패턴을 찾음
} else {
j++; // 아직 패턴의 끝이 아니므로 다음 문자로 이동
}
}
}
return false; // 패턴을 찾지 못함
}
}
마무리
코드와 설명이 부족할수 있습니다. 코드를 보시고 문제가 있거나 코드 개선이 필요한 부분이 있다면 댓글로 말해주시면 감사한 마음으로 참고해 코드를 수정 하겠습니다.
Junior backend developer