16172번: 나는 친구가 적다 (Large)

문제 출처 : https://www.acmicpc.net/problem/16172

16172번: 나는 친구가 적다 (Large)

언어 : Kotlin

 

문제 설명 :

친구가 적은 성민이는 수업에 결석해도 시험이나 과제에 대한 정보를 제대로 얻을 수 없었다. F 학점을 받을 위기까지 아슬아슬하게 결석일 수를 유지하던 성민이는, 어느 날 갑자기 영문도 모른 채 쪽지시험을 보게 되었다!

갑작스러운 쪽지 시험으로 마음이 급해진 성민이는 매직아이를 사용해 벼락치기를 하기로 한다.

성민이가 듣는 과목의 교과서는, 알파벳 소문자(a-z)와 알파벳 대문자(A-Z)로만 이루어져 있다. 성민이가 교과서에서 찾고자 하는 키워드도 역시 알파벳 소문자와 대문자로만 이루어져 있다. 하지만, 성민이에겐 큰 문제가 생겼다. 결석한 날의 수업 내용을 친구에게 빌려 필기를 하던 중, 교과서에 숫자(0-9)를 적어버린 것이다.

키워드를 찾기 힘들어 패닉에 빠진 성민이는 몇 안 되는 친구인 당신에게 도움을 요청했다. 성민이를 도와, 교과서에서 성민이가 찾고자 하는 키워드의 존재 여부를 알려주자.

 

입력 :

첫 번째 줄에는 알파벳 소문자, 대문자, 숫자로 이루어진 문자열 S가 주어진다. (1 ≤ |S| ≤ 200,000) 두 번째 줄에는 성민이가 찾고자 하는 알파벳 소문자, 대문자로만 이루어진 키워드 문자열 K가 주어진다. (1 ≤ |K| ≤ 200,000)

단, 입력으로 들어오는 키워드 문자열 K의 길이는, 교과서의 문자열 S보다 짧거나 같다.

 

출력 :

첫 번째 줄에 성민이가 찾고자 하는 키워드가 교과서 내에 존재하면 1, 존재하지 않으면 0을 출력한다.

 

제한 사항 :

• 시간 제한 : 1초 (추가 시간 없음)
• 메모리 제한 : 128MB

 

입출력 예 :

입력	출력
1q2w3e4r5t6y qwerty	1
1ovey0uS2 veS	0

 

풀이 : 

처음에 단순히 replace 후, contain으로 판별했다가 시간초과를 겪었다.

시간 제한 때문에 문자열 매칭 알고리즘인 KMP 알고리즘을 사용하게 되었다.

 

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    val s = readLine().replace("[0-9]".toRegex(), "")
    val k = readLine()

    bw.write(if (kmp(s, k)) "1" else "0")
    bw.flush()
    bw.close()
}

fun kmp(parent: String, pattern: String): Boolean {
    val table = makeTable(pattern)
    var check = false
    var idx = 0

    for (i in parent.indices) {
        while (idx > 0 && parent[i] != pattern[idx]) idx = table[idx - 1]
        if (parent[i] == pattern[idx]) {
            if (idx == pattern.length - 1) {
                check = true
                idx = table[idx]
            } else {
                idx++
            }
        }
    }

    return check
}

fun makeTable(pattern: String): IntArray {
    val table = IntArray(pattern.length) { 0 }
    var idx = 0

    for (i in 1 until table.size) {
        while (idx > 0 && pattern[i] != pattern[idx]) idx = table[idx - 1]
        if (pattern[i] == pattern[idx]) table[i] = ++idx
    }

    return table
}