[Swift 알고리즘] 백준 1339 (단어 수학)

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

1339번: 단어 수학

예비군 조기퇴소 한 날 나이스~

 

문제

민식이는 수학학원에서 단어 수학 문제를 푸는 숙제를 받았다.

단어 수학 문제는 N개의 단어로 이루어져 있으며, 각 단어는 알파벳 대문자로만 이루어져 있다. 이때, 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제이다. 같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다.

예를 들어, GCF + ACDEB를 계산한다고 할 때, A = 9, B = 4, C = 8, D = 6, E = 5, F = 3, G = 7로 결정한다면, 두 수의 합은 99437이 되어서 최대가 될 것이다.

N개의 단어가 주어졌을 때, 그 수의 합을 최대로 만드는 프로그램을 작성하시오.

입력

첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 10개이고, 수의 최대 길이는 8이다. 서로 다른 문자는 서로 다른 숫자를 나타낸다.

출력

첫째 줄에 주어진 단어의 합의 최댓값을 출력한다.

 

 

요약

밑에서 부터가 정확한 풀이

 

해결 방법 

1처음 해결 방법 (틀림)

Ex) GCF ACDEB

 

배열 세개를 활용하여 푼다.

더하려는 알파벳이 담겨있는 배열을 만든다.

arr1 = [[A], [C], [D,G], [C,E], [B,F]]

 

arr1을 참고하여 각 알파벳 마다 위치된 인덱스를 배열로 만든다.(dictionary) 

arr2 = [ ["A" : [4]], ["C" : [3, 1]], ["B" : [0]], ["D" : [2]], ["E" : [1]], ["F" : [0]], ["G" : [2]]]

 

 

arr1에서 반복문을 돌린다.

1.  arr1 에서 가중치를 주는데 arr2를 참고하여 만든다. 이 때 값들을 정렬해야하는데 정렬은 후순위에 나오는 값들을 참고하여 만든다.

예를들어  arr1의 값이(arr1[ind])"ABCD"라고 가정해보자. 그리고 arr2의 값을 다음과 같이 가정해보자 "A" : [4] , "B" : [4, 1] , "C" : [4, 1, 0] , "D" : [4, 2]  우리는 이 값들을 정렬시켜서 활용하면 가중치를 활용하는 것으로 볼 수 있다. 정렬하게 된다면...

-> "D" : [4, 2] "B" : [4, 1] "C" : [4, 1, 0] "A" : [4] 순으로 정리된다.

이 정렬된 배열에서 앞 값부터 현재 줄 수 있는 값의 최대를 준다. (intArr = [9, 8, 7, 6 ... 1] 에서 제일 앞 값을 빼서 준다.)

이것을 다시 arr3에 기재한다. arr3 = [["D" :  9], ["B" : 8], ["C" : 7], ["A" : 6]] 그리고  intArr은 [5, 4, 3, 2, 1]

 

2. 사실 1번보다 선행해야 하는 것은 현재 arr3[알파벳]의 값이 기재되어 있는지를 확인하는 것이다.

 

그것을 코드로 나타내면?

func sol() {
    let inputN = Int(readLine()!)!
    var targetInputArr:[[String]] = []
    for _ in 0..<inputN {
        let tempInput = readLine()!.reversed().map{String($0)}
        targetInputArr.append(tempInput)
    }
    var indArr:[[String]] = Array(repeating: [], count: 8)
    var stArr:[[Int]] = Array(repeating: [], count: 26)
    
    let alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ".map{String($0)}
    var alphabetDict = [String:Int]()
    var intArr = [Int : String]()
    for (ind, val) in alphabet.enumerated() {
        alphabetDict[val] = ind
        intArr[ind] = val
    }
    
    for i in targetInputArr {
        for (ind, val) in i.enumerated() {
            indArr[ind].append(val)
            stArr[alphabetDict[val]!].append(ind)
        }
    }
    //print(indArr)
    //print(stArr)
    
    var resDict = [String:Int]()
    
    var resIntArr = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
    for i in indArr.reversed() {
        if i == [] {continue}
        var tempArr:[String] = []
        for j in i {
            if resDict[j] == nil {
                tempArr.append(j)
            }
        }
        var tempIndArr:[Int :[Int]] = [:]
        for j in tempArr {
            
            tempIndArr[alphabetDict[j]!] = stArr[alphabetDict[j]!]
        }
        tempIndArr.sorted { firstDict, secondDict in
            firstDict.value.reduce(0){$0 + $1} + firstDict.value.count > secondDict.value.reduce(0){$0 + $1} + secondDict.value.count
        }
        for j in tempIndArr {
            resDict[intArr[j.key]!] = resIntArr.removeFirst()
        }
        //print(tempIndArr)
       
    }
    //print(resIntArr)
    //print(resDict)
    var sum = 0
    for i in targetInputArr {
        let tempNode = i.reversed().map{String(resDict[$0]!)}.joined(separator: "")
        print(tempNode)
        sum += Int(tempNode)!
    }
    print(sum)
}

sol()

 

 이렇게 된다. 아마 print부분을 살려서 코딩하면 과정이 쉽게 보일 것이다.

 

그러나 여기서 반례가 생겼다. 반례는

 

10
ABB
BC
BC
BC
BC
BC
BC
BC
BC
BC

 

이유는 가중치를 생각할 때 자리수 별로 생각해야한다. 위에 코드는 단순하게 생각한 것이기에 반례를 실행할 경우 A가 9가 나오지만 사실 B가 9가 나와야 최대가 나온다. 이를 해결하기 위해서 다음과 같이 생각해본다

 

 

2 다른 해결방법(맞음)

sum = 100 * A + 10 * 10 * B + B + 9 * C 로 말이다. 이를 계산하면 sum = 100A + 101B + 9C 이다. 따라서 이를 Dict로 가두어 생각하여 계싼하면 편할 것이다. 

resArr["B"] = 9, rsArr["A"] = 8 ...

 

 

아래는 주석을 달아놓은 코드이다. 

func sol3() {
    let inputN = Int(readLine()!)!
    var targetInputArr:[[String]] = []
    var alphabetWeight:[String : Int] = [:]
    let alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ".map{String($0)}
    
    for (_, val) in alphabet.enumerated() { //alphabetWeight["A"] = 0 이런식으로 초기화
        alphabetWeight[val] = 0
    }
    for _ in 0..<inputN {
        let tempInput = readLine()!.reversed().map{String($0)} // input = ["A", "B", "C"...]
        targetInputArr.append(tempInput)
        var tempInd = 1
        for i in tempInput { //각 알파벳 마다 가중치를 더해줌
            alphabetWeight[i]! += tempInd //1의 자리일 때는 1, 10의 자리일때는 10...
            tempInd *= 10
        }
    }
    let sortedDict = alphabetWeight.sorted { (dic1, dic2) in
        return dic1.value > dic2.value
    } //(key: "A", value: 10000), (key: "C", value: 1010), (key: "D", value: 100),
    //(key: "G", value: 100), (key: "E", value: 10), (key: "B", value: 1), (key: "F", value: 1)처럼 dict가 생성(정렬되어있는거)
    
    var resIntArr = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
    var resDict:[String : Int] = [:]
    for i in sortedDict {
        if i.value == 0 {
            break //모든 알파벳에 대해서 초기화를 해줬기에, 0나오면 break
        }
        resDict[i.key] = resIntArr.removeFirst() //resDict["알파벳"] = 현재 배치되지 않은 숫자중에서 제일 큰 숫자
    }
    //print(resDict)
    
    var sum = 0
    for i in targetInputArr {
        let node = i.reversed().map{String(resDict[$0]!)}.joined(separator: "")
        sum += Int(node)!
        
    }
    print(sum)
}
sol3()

 

감삼당~