[Swift][비트마스킹] 백준 1062번 (가르침)

요구능력

조합, 비트마스킹

 

문제풀이

나혼자 처음에 이해를 못한건가 싶기도한데..

anta tica를 기본으로 깔고 중간에 있는 단어들중에서 k개를 배운다는줄 알았다.

그게 아니고 anta tica포함 k개였다.

 

C++언어로는 완탐조합만 돌려도 시간초과가 나오지 않을것이다.

하지만, 스위프트로 풀기위해서는 비트마스킹을 사용해야한다.

 

1) 문장을 입력받을 때 각 문장마다 단어를 비트마스킹으로 추가해줬다.

for i in 0..<n{
    let a = readLine()!.map{String($0)}
    for j in a{
        wordsBit[i] |= 1 << (Int(Character(j).asciiValue! - Character("a").asciiValue!))
    }
}

 

2) k가 5보다 작게 들어오면 anta tica마저 배우지 못하기 때문에 읽을 수 있는 단어개수가 0개이다.

그래서 0을 리턴해줬고,

비트마스킹을 사용해서 alphabet에 읽을 수 있는 단어들을 저장해 줄 것이다.

그리고 k에서는 antic를 추가했으니 5를 빼준다.

func solution() -> Int{
    if k < 5{
        return 0
    }
    alphabet |= 1 << (Int(Character("a").asciiValue! - Character("a").asciiValue!))
    alphabet |= 1 << (Int(Character("n").asciiValue! - Character("a").asciiValue!))
    alphabet |= 1 << (Int(Character("t").asciiValue! - Character("a").asciiValue!))
    alphabet |= 1 << (Int(Character("i").asciiValue! - Character("a").asciiValue!))
    alphabet |= 1 << (Int(Character("c").asciiValue! - Character("a").asciiValue!))
    k = k - 5
    dfs(0, 0)
    
    return result
}

 

3)  조합을 사용했다.

어차피 사용할 수 있는 알파벳은 순서가 필요없기 때문이다.

 

func dfs(_ depth: Int, _ start: Int){
    var count = 0
    if depth == k{
        for i in 0..<n{
            if wordsBit[i] & alphabet == wordsBit[i]{
                count += 1
            }
        }
        result = max(result, count)
        return
    }
    for i in start...25{
        if (alphabet & (1 << i)) == 0{
            alphabet |= (1 << i)
            dfs(depth + 1, i)
            alphabet &= ~(1 << i)
        }
    }
}

 

후기

처음에 조합으로 그냥 완탐돌았다가 시간초과나서.. 비트마스킹에 대해 공부해보는 좋은시간을 가진것같다.

언제 비트마스킹을 사용해야되는건지는.. 아직감이 안잡혀서 코테에서는 아직 못쓸거같다.

 

코드

import Foundation
var nk = readLine()!.split(separator: " ").map{Int(String($0))!}
let n = nk[0]
var k = nk[1]
var result = 0
var alphabet = 0
var wordsBit = Array(repeating: 0, count: 50)
for i in 0..<n{
    let a = readLine()!.map{String($0)}
    for j in a{
        wordsBit[i] |= 1 << (Int(Character(j).asciiValue! - Character("a").asciiValue!))
    }
}
func dfs(_ depth: Int, _ start: Int){
    var count = 0
    if depth == k{
        for i in 0..<n{
            if wordsBit[i] & alphabet == wordsBit[i]{
                count += 1
            }
        }
        result = max(result, count)
        return
    }
    for i in start...25{
        if (alphabet & (1 << i)) == 0{
            alphabet |= (1 << i)
            dfs(depth + 1, i)
            alphabet &= ~(1 << i)
        }
    }
}
func solution() -> Int{
    if k < 5{
        return 0
    }
    alphabet |= 1 << (Int(Character("a").asciiValue! - Character("a").asciiValue!))
    alphabet |= 1 << (Int(Character("n").asciiValue! - Character("a").asciiValue!))
    alphabet |= 1 << (Int(Character("t").asciiValue! - Character("a").asciiValue!))
    alphabet |= 1 << (Int(Character("i").asciiValue! - Character("a").asciiValue!))
    alphabet |= 1 << (Int(Character("c").asciiValue! - Character("a").asciiValue!))
    k = k - 5
    dfs(0, 0)
    
    return result
}

print(solution())