백준 - 문서 검색(Swift)

문제 이름

 

 

 문제 설명

 

https://www.acmicpc.net/problem/1543

1543번: 문서 검색

 

 처음 나의 풀이

 

처음에는 단순히 첫 번째부터 탐색하여 target과 맞지않으면 idx를 리셋하는 식으로 문제를 풀었다. 그러다가 넘긴값이 target[idx]값과 같다면 이어서 인덱스탐색을 해줘야하는 반례를 찾았다.

하지만 그래도 테스트케이스를 전부 통과하지 못했다.

 

그래서 다른 사람의 풀이를 찾아봤다.

 

import Foundation

let document = readLine()!.map{String($0)}
let target = readLine()!.map{String($0)}
var cnt = 0
var idx = 0
for i in 0...document.count-1 {
    if target[idx] == document[i] {
        idx += 1
        if idx == target.count {
            cnt += 1
            idx = 0
        }
    } else { 
        idx = 0
        if target[idx] == document[i] {
            idx += 1
        }
    }
}

print(cnt)

 

 

 다른 사람의 풀이

 

import Foundation

var doc = readLine()!
let target = readLine()!
var cnt = 0
var index = doc.range(of: target)?.upperBound

while index != nil {
    cnt += 1
    doc = String(doc[index!...])
    index = doc.range(of: target)?.upperBound
}

print(cnt)

 

 

스위프트에서 문자열을 어떻게 다루고 있는지 알 수 있는 풀이이다.

먼저 문자열에 대해 range(of:)를 하면 배열로 따졌을때 0..<찾는 문자열의 끝+1이 된다. 즉 여기서 upperBound를 하게되면 찾는 문자열의 끝 +1인 인덱스가 나오게 되고 doc[index!...]를 하게되면 그 부분부터 다시 문자열을 구성하게 된다.

 

그리고 새로 알게된 사실은 

var str: String = "abc"일때 str[str.endIndex...]는 런타임에러를 발생시키지 않는 다는 것이다. 이 때문에 위의 while문에서 doc[index!...]를 할때 index가 boundary외의 값이라도 에러를 발생시키지 않는것이다.

 

 

 

 

 또 다른사람의 풀이

 

나의 방법에서 반례를 못찾을때 그냥 전부를 탐색하는 방법이 있다.

그 방법이 아래와 같은 방법이다. 

항상 완전탐색도 방법이라는 것을 인지하고 문제를 풀어야겠다.

 

import Foundation

var doc = Array(readLine()!)
let target = Array(readLine()!)

func findMatching(_ idx: Int) -> Int {
    var i = idx
    var tIdx = 0
    var cnt = 0
    while i < doc.count {
        if target[tIdx] == doc[i] {
            if tIdx == target.count-1 {
                cnt += 1
                tIdx = 0
            } else {
                tIdx += 1
            }
        } else {
            tIdx = 0
        }
        i += 1
    }
    return cnt
}

var maxVal = 0
for i in 0..<doc.count {
    maxVal = max(maxVal, findMatching(i))
}

print(maxVal)