[백준/Swift] 16508번: 전공책

 

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

16508번: 전공책

 

브루트포스 문제.

백트랙킹으로 풀었는데 정말 많이 틀렸다..^^

지금 생각해 보면 사실 그렇게 틀릴 일이 없는데,, 백트래킹 문제를 꽤 오랫동안 안 풀었더니 더 헤맸던 것 같다

다시 공부하자!

 

처음에는 만들고자 하는 단어와 전공책 제목과 직접적으로 비교하고, removeLast(), remove() 메소드를 사용해서 삭제해 주는 쪽으로 했다. 그런데 이렇게 하니 시간초과 발생(91%에서..😭).

c++에서는 이런 문제를 alphabet 배열을 만들어서 진행하기도 했기 때문에 이번에도 그런 식으로 접근해봤다. 

 

func searchWord(count: Int, sum: Int) {
    if n == count {
        if checkWord() { //만약 선택한 책에서 단어를 만들어낼 수 있다면
            answer = min(answer, sum)
        }
        return
    }
    let tmp = books[count].0.map{String($0)}
    for i in 0..<tmp.count {
        let index = Int(UnicodeScalar(tmp[i])!.value) - Int(UnicodeScalar("A").value)
        bookAlpha[index] += 1
    }
    searchWord(count: count + 1, sum: sum + books[count].1)
    for i in 0..<tmp.count {
        let index = Int(UnicodeScalar(tmp[i])!.value) - Int(UnicodeScalar("A").value)
        bookAlpha[index] -= 1
    }
    searchWord(count: count + 1, sum: sum)
}

searchWord(count: 0, sum: 0)

 

처음에는 선택할 전공책 1권~n권을 따로 정했었는데, 시간초과가 계속 발생해서 다른 분의 코드를 살펴봤다... ^.ㅠ

위 코드를 보면 알 수 있듯이 

 

-----------------------------------------

선택한 전공책의 제목 알파벳 개수 카운팅

재귀호출(현재 전공책을 선택한 경우)

위에서 선택했던 전공책 제목 알파벳 개수 차감

재귀호출(현재 전공책을 선택하지 않은 경우)

-----------------------------------------

 

이런 형태를 가진다. 직접 해보면 알겠지만 이렇게 하면 전공책을 선택하는 모든 경우의 수가 나온다.

 

func checkWord() -> Bool {
    for i in 0..<26 {
        if talpha[i] > bookAlpha[i] { return false }
    }
    return true
}

 

checkWord 메소드에서 만들고자 하는 단어를 만들 수 있는지 체크한다.

searchWord 메소드에서 bookAlpha 배열에 선택한 전공책 제목 알파벳 개수를 카운팅을 해놨는데

각 알파벳을 체크하는데, 만약 만들고자 하는 단어의 알파벳 개수가 더 많으면 return false

선택한 전공책 제목으로는 만들고자 하는 단어를 만들 수 없다는 의미다.

 

 

[전체 코드]

import Foundation

/*
 가장 적은 비용으로 민호가 원하는 단어를 만들기 위해 어떤 전공책을 선택해야 할까?
 단어를 만들기 위해 선택해야 하는 전공책의 가장 적은 가격의 합 구하기
 */

//input
let t = readLine()!.map{ String($0) }
let n = Int(readLine()!)!
var books = [(String, Int)]()
var talpha = [Int](repeating: 0, count: 26)
var bookAlpha = [Int](repeating: 0, count: 26)
var answer = Int.max

for i in 0..<t.count {
    let index = Int(UnicodeScalar(t[i])!.value) - Int(UnicodeScalar("A").value)
    talpha[index] += 1
}

for _ in 0..<n {
    let input = readLine()!.split(separator: " ").map{ String($0) }
    books.append((input[1], Int(input[0])!))
}

//list에 있는 책들로 단어를 만들 수 있는지 체크하는 함수
func checkWord() -> Bool {
    for i in 0..<26 {
        if talpha[i] > bookAlpha[i] { return false }
    }
    return true
}

func searchWord(count: Int, sum: Int) {
    if n == count { //정한 책의 개수를 채웠을 경우
        if checkWord() { //만약 선택한 책에서 단어를 만들어낼 수 있다면
            answer = min(answer, sum)
        }
        return
    }
    let tmp = books[count].0.map{String($0)}
    for i in 0..<tmp.count {
        let index = Int(UnicodeScalar(tmp[i])!.value) - Int(UnicodeScalar("A").value)
        bookAlpha[index] += 1
    }
    searchWord(count: count + 1, sum: sum + books[count].1)
    for i in 0..<tmp.count {
        let index = Int(UnicodeScalar(tmp[i])!.value) - Int(UnicodeScalar("A").value)
        bookAlpha[index] -= 1
    }
    searchWord(count: count + 1, sum: sum)
}

searchWord(count: 0, sum: 0)

if answer == Int.max { answer = -1 }
print(answer)

 

 

새로운 백트랙킹 방법을 알게된 것 같다. 

다른 문제에도 사용해봐야지!

 

 

고군분투한 흔적... 너무 힘들었다..^^