백준 1543 문서 검색

출처: www.acmicpc.net/problem/1543

분류: 그리디

---

접근방식

문자열 매칭 문제 입니다. 겹치지 않게 문자열을 찾으면 됩니다.

문서 길이가 2500정도 밖에 안되서 단순 매칭으로도 해결할 수 있는 문제입니다.

문제는 탐색의 시작을 반드시 0번부터 할 필요는 없다는 것이죠.

첫번째부터 탐색한거보다 그 이후부터 탐색을 시작해서 더 경우가 많아지는 반례는 찾지 못했습니다... 
앞에서 탐색한 것 때문에 뒤에 문자를 더 찾지 못해 한 개를 손해 보더라도 앞에서 탐색한거랑 쌤쌤으로 개수는 똑같을 것 같은데....
한 개이상 손해볼 수가 있는지 반례를 잘 찾지 못하겠습니다 😭
실제로도 c++ 같은 다른 분들의 풀이를 보니 그냥 첫번째부터 탐색해서 통과하셨더라구요...
채점 방식이 예전과 달라진 것인지.. 무튼 Swift에서는 그렇게 해서는 통과가 안되더라구요 ㅠ_ㅠ

 

아무튼 그래서 문서의 시작부터 끝까지 각각을 시작점으로 했을 때 찾을 수 있는 매칭결과 중에 최대가 답이 됩니다.

이제 각각을 시작점으로 했을 때 실제 탐색 방법은

여러 방식으로 구현할 수 있습니다. 현재 인덱스부터 찾아나가다가 일치하는 단어를 찾으면 찾은 단어의 길이만큼 인덱스를 건너뛰는 방식으로 찾을 수도 있구요, 하지만 Swift는 이런 방식이 매우 취약하기 때문에
이 방식 보다는 문서의 인덱스는 증가시켜주면서 찾는 단어의 인덱스로 따로 둬서 각 단어가 일치하면 단어의 인덱스도 증가시켜주고 다르면 단어의 인덱스는 0으로 만들면서 단어의 길이만큼 찾아나가는 방식으로도 할 수 있습니다.

 

해결방법 

Swift의 취약점인 String을 다루는 문제이기 때문에 어떻게 푸냐에 따라서 시간 차이가 매우 심하게 날 수 있습니다.

단순히 두 단어를 비교하는 문제이기 때문에 처음 문자를 받을 때 Array로 묶어서 [String.Element]로 해서 비교하면 빠르게 할 수 있습니다. 문자열 인덱스로 가지고 찾아가면.. 약 30배 정도 더 느린 것 같더라구요 ; ; ;

let text = Array(readLine()!)
let word = Array(readLine()!)

func findMatching(index idx: Int) -> Int {
    var i = idx
    var wIdx = 0
    var matching = 0
    while i < text.count {
        if text[i] == word[wIdx] {
            if wIdx == word.count-1 {
                matching += 1
                wIdx = 0
            } else {
                wIdx += 1
            }
        } else {
            wIdx = 0
        }
        i += 1
    }
    return matching
}


var result = 0
for i in 0..<text.count {
    let matching = findMatching(index: i)
    result = max(result, matching)
}
print(result)

 

문자열 인덱스로 찾은 풀이, 위 코드는 20ms로 통과한대 반해 이건 648ms ;;;

let text = Array(readLine()!)
let word = Array(readLine()!)

// 시간 매우 많이 걸림 648ms? 약.. 30배 넘게 느림..
func findMatching(text: String) -> Int {
    guard text.count >= word.count else { return 0 }
    var temp = 0
    var matching = 0
    for t in text {
        if t == word[temp] {
            if temp == word.count-1 {
                matching += 1
                temp = 0
            } else {
                temp += 1
            }
        } else {
            temp = 0
        }
    }
    return matching
}

var result = 0
for i in 0..<text.count {
    let matching = findMatching(text: String(text.dropFirst(i)))
    result = max(result, matching)
}
print(result)

 

배운점

처음엔 Index를 탐색하게 만든 extension을 사용했었는데, 

이렇게 하니 타임아웃.. 인덱스를 while로 돌면서 찾는거라 가뜩이나 느린데 상당히 시간이 많이 걸리는 방법이었다.

처음엔 속도 문젠가 해서 문자열 탐색 알고리즘도 찾아보긴 했는데 그렇게까지 하지 않아도 그냥 풀리는 문제긴 했다.

문자열 탐색 알고리즘도 여러가지가 있는 것 같던데 

KMP 알고리즘도 해볼만 한 것 같다.

직접 해봐야하는데... 지금은 좀 귀찮다.. 다음에 공부해서 이 방법으로 다시 풀어보자