[Algorithm] 백준 - 1062번 가르침 (Swift)

문제 소개

알파벳을 가르칠 수 있고, 아래와 같이 주어질때 6개의 알파벳을 알려줘서 최대로 알수 있는 단어의 개수를 출력하는 문제이다.

3 6
antarctica
antahellotica
antacartica

// 2

 

문제 풀이

비트마스크로 해결했다. dfs를 통해 bitmask를 만들고, k만큼 알려줬다면 countReadbleWords 함수를 통해 읽을 수 있는 단어 개수의 최댓값을 출력한다.

import Foundation

let nk = readLine()!.split(separator: " ").map { Int($0)! }
let (n, k) = (nk[0], nk[1])
var words = [Int]()

for _ in 0..<n {
    let word = readLine()!
    var bitmask = 0
    
    for chr in word {
        bitmask = bitmask | (1 << Int(chr.asciiValue! - 97))
    }
    
    words.append(bitmask)
}

if k < 5 {
    print(0)
    exit(0)
}

let base: [Character] = ["a", "n", "t", "i", "c"]
var baseBitmask = 0

for chr in base {
    baseBitmask = baseBitmask | (1 << Int(chr.asciiValue! - 97))
}

func countReadableWords(_ bitmask: Int) -> Int {
    var count = 0
    for word in words {
        if (word & bitmask) == word {
            count += 1
        }
    }
    return count
}

var maxCount = 0

func dfs(_ index: Int, _ bitmask: Int, _ depth: Int) {
    if depth == k - 5 {
        maxCount = max(maxCount, countReadableWords(bitmask))
        return
    }
    
    for i in index..<26 {
        if (bitmask & (1 << i)) == 0 {
            dfs(i + 1, bitmask | (1 << i), depth + 1)
        }
    }
}

dfs(0, baseBitmask, 0)
print(maxCount)

 
dfs를 통해 bitmask를 넣어주는 과정에서 시간을 많이 잡아먹을 줄 알았는데 빠르게 나왔다. 최대 2^20 이라 그런것 같다.