[Swift][Math] 백준 1339번 (단어 수학)

요구능력 : Math공식

 

코드설명 : 

 

문제를 이해하는건 어렵지않다.

 

입력받는거부터 보면 단어를 떨어뜨려서 주지않고 붙여서준다.

이럴때는 한줄입력받고 그대로 for문에 넣어서 아래와 같이 쪼개주면 된다.

for i in 0..<n{
    let read = readLine()!
    for j in read{
        arr[i].append(j)
    }
}

 

그리고 나는 딕셔너리를 사용해서 문제를 풀것이라서 딕셔너리에 우선 키를 넣어놓기위해 for문으로 입력받은 배열을 다 돌면서 알파벳을 넣어줬다.

for i in 0..<n{
    for j in 0..<arr[i].count{
        dict[arr[i][j]] = 0
    }
}

 

쉽게생각해보면 수학공식으로 풀리는 문제였다.

간단히 설명하면 만약, 아래와같은 입력이 들어왔다고 해보자.

2

ABC

DAB

만약 A가 9, B가 8, C가 7, D가 6 이었다고 치면

987 + 698이 된다.

그렇다는건 맨앞에있는 A와 D는 100의자리 수라는 의미이고

그 다음은 10의자리 그 다음은 1의자리이다.

그 말인 즉슨, 

100A + 10B + C 

+ 100D + 10A + B 라는 식이 성립한다는 말이고 여기서 가장 큰 수를 곱하는 알파벳이 가장 커야 최대값이 나올것이다.

그럼,

110A + 100D + 11B + C 가 나오게되는데

A = 9, D = 8, B = 7, C = 6을 넣어주면 최대의 값이 나오게된다.

딕셔너리의 value값으로

dict[A] = 110

dict[D] = 100

dict[B] = 11

dict[C] = 1 이 들어가게 된다.

그럼이제 내림차순으로 정렬해서 각 value에 9부터 1까지 곱해주고

sum에 합계를 더해주면 정답이 나오게 된다.

for i in 0..<n{
    for j in 0..<arr[i].count{
        dict[arr[i][j]]! += Int(pow(10, Double(arr[i].count - j - 1)))
    }
}

var j = 9
for i in dict.sorted(by: {$0.value > $1.value}){
    sum += i.value * j
    j = j - 1
}

 

 

 

후기 :  처음에는 백트래킹으로 접근했는데 잘 안풀려서 구글링해보니까 되게 쉬운방법이있어서 이 방법을 채택했다.. 쉬운 방법이지만 뭔가 야매같은..? 느낌이 없지않아있어서 다음번에는 백트래킹으로 풀어봐야겠다.

import Foundation
let n = Int(String(readLine()!))!
var arr: [[Character]] = Array(repeating: [], count: n)
var dict = [Character:Int]()
var sum = 0
for i in 0..<n{
    let read = readLine()!
    for j in read{
        arr[i].append(j)
    }
}

for i in 0..<n{
    for j in 0..<arr[i].count{
        dict[arr[i][j]] = 0
    }
}

for i in 0..<n{
    for j in 0..<arr[i].count{
        dict[arr[i][j]]! += Int(pow(10, Double(arr[i].count - j - 1)))
    }
}

var j = 9
for i in dict.sorted(by: {$0.value > $1.value}){
    sum += i.value * j
    j = j - 1
}
print(sum)