16500번: 문자열 판별

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

16500번: 문자열 판별

언어 : Kotlin

 

문제 설명 :

알파벳 소문자로 이루어진 문자열 S와 단어 목록 A가 주어졌을 때, S를 A에 포함된 문자열을 한 개 이상 공백없이 붙여서 만들 수 있는지 없는지 구하는 프로그램을 작성하시오. A에 포함된 단어를 여러 번 사용할 수 있다.

 

입력 :

첫째 줄에 길이가 100이하인 문자열 S가 주어진다. 둘째 줄에는 A에 포함된 문자열의 개수 N(1 ≤ N ≤ 100)이 주어진다. 셋째 줄부터 N개의 줄에는 A에 포함된 단어가 한 줄에 하나씩 주어진다. A에 포함된 문자열은 알파벳 소문자로만 이루어져 있고, 길이는 100을 넘지 않는다.

 

출력 :

A에 포함된 문자열로 S를 만들 수 있으면 1, 없으면 0을 출력한다.

 

제한 사항 :

• 시간 제한 : 2초
• 메모리 제한 : 512MB

 

입출력 예 :

입력	출력
softwarecontest 2 software contest	1

 

풀이 : 

문제를 잘못 이해해서 처음에 좀 틀렸다.

뒤에서부터 시작하여 dp[j]가 1이고 s.substring(i, j)가 set에 포함되어 있다면 dp[i]를 1로 바꾼다.

하지만 반복문을 처음 시작했을때는 dp가 전부 0으로 초기화 되어있으므로 넘어가고 마지막의 if문으로 간다.

 

s.substring(i)가 set에 포함되어 있다면 dp[i]를 1로 바꾼다.

substring은 시작인덱스에서 부터 String의 마지막까지 자르는 것이기 때문에 예시로 나온 softwarecontest 기준으로 하면, 반복문의 첫번째 s.substring(i)는 맨 뒤 문자인 t이다.

 

하지만 알다시피 a에 들어간 문자는 software와 contest이므로 i가 8이 되어 substring될 때까진 진전없이 반복된다.

i가 8이 될 경우, contest가 반환되는데 이는 set에 포함되어 있으므로 dp[8] = 1이 된다.

 

이 다음에 i는 7로 떨어지게 되고 j는 i + 1 이므로 8이 되는데, dp[8]은 1이므로 그 안의 if문을 판별하게 된다.

s.substring(7, 8)은 e 이므로 set에 포함되어 있지 않아 진전이 없어진다. (substring(start, end) start만 들어가면 문자열의 끝까지 자르지만, end index가 추가되면 그 이전까지만 자른다. 즉 start until end인 셈.)

이후에도 dp[8] = 1 이므로 계속 substring하게 되는데

 

e - re - are - ware - tware - ftware - oftware - software

 

이렇게 계속 반복하여 i가 0이 되면 s.substring(0, 8)은 software가 되고, 이는 set에 포함되어 있기에 dp[0] = 1이 된다.

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()
    val set = hashSetOf<String>()
    repeat(readLine().toInt()) {
        set.add(readLine())
    }

    val dp = IntArray(s.length)
    for (i in s.lastIndex downTo 0) {
        for (j in i + 1 .. s.lastIndex) {
            if (dp[j] == 1) if (set.contains(s.substring(i, j))) dp[i] = 1
        }

        if (set.contains(s.substring(i))) dp[i] = 1
    }

    bw.write("${dp[0]}")
    bw.flush()
    bw.close()
}