14426: 접두사 찾기
문자열 S의 접두어는 S의 처음부터 부분 문자열을 의미합니다. 예를 들어 S = “codeplus”의 접두어에는 “code”, “co”, “codepl” 및 “codeplus”가 포함되지만 “plus”, “s” “, “cude” 및 “crud”는 접두사가 아닙니다. 총 N자
www.acmicpc.net
간략한 문제 요약
N개의 줄에는 세트 S에 포함된 문자열이 제공됩니다. 그리고 다음 M개의 줄에는 확인해야 하는 문자열이 제공됩니다. 문제는 적어도 하나의 접두사 S를 포함하는 검사할 문자열의 수를 찾는 것입니다.
예를 들어
S = “codeplus”, “cow” 및 M = “code”, “co”, “crud”, code, co인 경우. 두 개는 S의 접두사에 해당합니다.
문제 해결 | PS 로그
let input = readLine()!.split{$0==" "}.map{Int(String($0))!}
let (n,m) = (input(0),input(1))
// S
let list = (0..<n).map { _ in readLine()! }.sorted()
// M
let texts = (0..<m).map{ _ in readLine()! }
입력을 배열로 가져오고,
처음에는 무차별 대입 방식으로 문제에 접근했습니다. 집합 M에서 검색할 각 문자열이 집합 S의 접두사에 해당하는지 여부를 식별했습니다.
print(texts.filter{
for str in list where str.hasPrefix($0) {
return true
}
return false
}.count)
그러나 시간 초과가 발생했습니다. 흠.. 더블파이어로 검색해보니 최악의 경우 시간복잡도가 10,000*10,000, 약 1억 연산인 줄 알았는데.. hasPrefix() 시간복잡도는 공식문서에 나와있지 않았다. 그런데 입력으로 주어지는 문자열의 길이가 500자까지라서 1억 * 500이라 타임아웃이 된 건 아닐까 싶었습니다.
그래서 시간 복잡도가 O(logn)인 이진 검색을 사용하려고 생각했습니다. 2개의 배열 리스트 중 하나인 texts를 정렬하면 정렬된 배열에 대해서만 이진 검색으로 수행할 수 있기 때문이다. +_+
func bs(_ target: String, list: (String)) ->Int {
var l = 0, r = list.count-1, m = 0
while l<r {
m = (l+r)/2
if target > list(m) { l = m + 1 }
else { r = m }
}
return r
}
이진 검색의 빠른 구현,
//S
let list = (0..<n).map { _ in readLine()! }.sorted()
세트 S를 정렬했습니다.
print(texts.filter{
return list(bs($0,list:list))
.hasPrefix($0) ? true : false
}.count)
그리고 각각의 텍스트 문자열(M set)에 대해 목록의 특정 요소의 인덱스를 이진 검색을 통해 반환한 후 목록의 어떤 요소가 가장 가까운지 알아낸 후 .hasPrefix()를 사용하여 다음을 확인합니다. 그것은 일치하고 번호를 저장합니다.
나는 그것을 느꼈다
비교할 수 있고 정렬 가능한 배열에서 무언가를 찾아야 하는 경우. 이분 검색을 사용하는 O(logn) 방법이 서문을 사용하는 O(n) 방법보다 낫다는 것을 알았습니다. 그리고 filter는 특정 조건에 맞는 원소를 배열로 반환하는데, 이때 count+_+를 통해 그 개수를 알아두는 것이 좋다.
암호
func bs(_ target: String, list: (String)) ->Int {
var l = 0, r = list.count-1, m = 0
while l<r {
m = (l+r)/2
if target > list(m) { l = m + 1 }
else { r = m }
}
return r
}
let input = readLine()!.split{$0==" "}.map{Int(String($0))!}
let (n,m) = (input(0),input(1))
let list = (0..<n).map { _ in readLine()! }.sorted()
let texts = (0..<m).map{ _ in readLine()! }
print(texts.filter{
return list(bs($0,list:list))
.hasPrefix($0) ? true : false
}.count)