[백준/Swift] 144256: 접두사 찾기 | PS일지

문제

14426번: 접두사 찾기

간단한 문제 요약

N개의 줄에 집합S에 포함된 문자열이 주어집니다. 그리고 다음 M개의 줄에는 검사해야 하는 문자열이 주어집니다. 검사해야 할 문자열 중에 S의 접두사에 적어도 한 개 이상 포함되는지 개수를 찾는 문제입니다.

 

예를들어 

 S = "codeplus", "cow"이고, M = "code", "co", "crud"일 때 code, co. 2개가 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집합의 prefix에 해당되는지 여부를 파악했습니다.

 

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)인 이분탐색을 사용하는 방법을 생각했습니다. 두 개의 배열  list, texts중 하나를 sort하면 sorted된 배열에 한정해서 이분 탐색으로 수행할 수 있기 때문입니다. +_+

 

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집합을 sort했습니다.

 

print(texts.filter{
  return list[bs($0,list:list)]
    .hasPrefix($0) ? true : false
}.count)

 

그리고 texts( M집합 ) 각각의 문자열에 대해 list의 어느 element와 근접하는지 이분 탐색을 통해 list의 특정 원소 index를 반환한 후 .hasPrefix()를 통해 일치하는지 여부를 파악해서 그 개수를 저장해나갔습니다.

 

느낀점

비교할 수 있고, 정렬할 수 있는 배열에서 무언가를 찾아야 한다면. 포문을 사용하는 방법O(n)보다 이분 탐색을 사용하는 방법O(logn)이 좋다는 것을 알게 되었습니다. 그리고 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)