백준 1339 단어 수학

출처: https://www.acmicpc.net/problem/1339

분류: 그리디

---

접근방식

기본적으로 글자를 체크하고 수를 만드는 방식은
글자를 키로하고 글자의 자리 수 배열(해당 문제에서 최대 8자리)을 만들어서
이 글자가 해당 자리수에 몇 번이 사용되었는지 체크했습니다. 그리고 이걸 가지고 수를 만드는 방식으로 접근했습니다.

이제 문제는 어떤 글자에 어떤 숫자를 할당할지 결정해야 합니다.
아마도 가장 일반적인 생각이자 실수하기 딱 좋은 가정은 가장 큰 자리 수의 숫자가 많은 글자에 가장 큰 수를 매칭시키는 것으로 생각할 수 있습니다. 아래 예를 생각해볼까요?

AA
BC

" 가장 큰 자리에 A 와 B가 1개씩 있어서 동률이고, 그 다음에 A가 한 번 더 있으니 A에 가장 큰 수인 9를 할당하면 되겠다 "
라고 생각할 수 있습니다. 하지만 단순히 이렇게 접근하면,

ABB
BB
BB
BB
BB
BB
BB
BB
BB
BB

와 같은 예에서는 가장 큰 자리수에 A 밖에 없으니 A에 가장 큰 9를 할당해버릴 수 있습니다.

하지만 이 경우 A = 9, B = 8 로 할당하면, 900 + 88 * 10 으로 1780 이고
A = 8, B = 9 로 할당하면 800 + 99 * 10 으로 1790이 되어서 반례가 됩니다.

따라서 저는 어차피 알파벳은 26개밖에 안되므로
글자마다 자리 수를 만들었을 때 합이 가장 큰 글자에 가장 큰 수를 매칭시키는 방법으로 해결했습니다.

 

해결방법

protocol Readable {
    func readSingleValue() -> String
    func readArray(with separator: Character) -> [String]
}

extension Readable {
    func readSingleValue() -> String {
        return readLine()!
    }
    
    func readSingleValue() -> Int {
        return Int(readLine()!)!
    }
    
    func readArray(with separator: Character) -> [String] {
        return readLine()!.split(separator: " ").map { String($0) }
    }
    
    func readArray(with separator: Character) -> [Int] {
        return readLine()!.split(separator: " ").map { Int(String($0))! }
    }
}

class BOJ1339: Readable {
    
    func input() {
        for _ in 0..<readSingleValue() {
            var string: String = readSingleValue()
            var digit = 0
            while !string.isEmpty {
                let number = string.removeLast()
                digits[number, default: [Int](repeating: 0, count: 8)][digit] += 1
                digit += 1
            }
        }
    }
    
    // MARK: Properties
    
    var digits = [Character: [Int]]()
    
    // MARK: Solution
    
    func solution() {
        input()
        let orderedDigits = orderDigits()
        var maxNumber = 9
        var result = 0
        for (_, counting) in orderedDigits {
            result += makeSum(number: maxNumber, counting: counting)
            maxNumber -= 1
        }
        print(result)
    }
    
    func power(_ number: Int, count: Int) -> Int {
        var powered = 1
        (0..<count).forEach { _ in powered *= number }
        return powered
    }
    
    func orderDigits() -> [(Character, [Int])] {
        return digits.sorted { (counting1, counting2) -> Bool in
            return makeSum(number: 1, counting: counting1.value) > makeSum(number: 1, counting: counting2.value)
        }
    }
    
    func makeSum(number: Int, counting: [Int]) -> Int {
        var result = 0
        for (digit, count) in counting.enumerated() {
            result += number * count * power(10, count: digit)
        }
        return result
    }
}

BOJ1339().solution()

 

 

배운점

놓치기 쉬운 반례를 배웠습니다. 최소한 입출력의 끝점 정도는 염두에 두고 예외를 생각해야겠습니다.

테스트 케이스를 많이 안 돌려주는 코테에서 이랬다고 생각하면 아찔하네요... 😱