[swift] 백준 - 15829번: Hashing

15829번: Hashing

문제 푸는 데 있어 도움이 되도록 나의 풀이와 개선된 풀이를 올립니다.
또한 풀이 후 다른 사람의 풀이를 보고 참고할만한 풀이도 올립니다.
- 문제에 따라 나의 풀이만 있을 수 있습니다.
- 해당 풀이들은 풀이 중 하나일 뿐 최선의 풀이는 아닐 수 있습니다.

 

---

 

문제 설명

 

해당 문제에 주어진 문자열을 해시값으로 만들기 위해

모듈로 연산의 속성을 이용해 풀 수 있었습니다.

 

모듈로 연산은 저희가 많이쓰는 '%'로

나누어 떨어졌을 때 나머지를 구하는걸 말하는데요.

 

해당 문제에서 모듈로 연산의 속성 중

(a * b) mod n = {(a mod n) * (b mod n)} mod n

를 모르면 부분점수 50점이 나왔고

해당 속성을 적용해서 푸니 100점이 나왔습니다.

 

그냥 풀면 문자열길이가 너무 길어 초과되나 봅니다.

 

---

 

나의 풀이(오답)

import Foundation

let _ = Int(readLine()!)!
var a = readLine()!.utf8.map { Int($0) - 96 }
var result = 0
for i in a.enumerated() {
    result += i.element * Int(pow(31.0, Double(i.offset)))
}
print(result)

 

해당 풀이는 pow함수에서 제곱수가 너무 커져서 부분점수만 나왔습니다.

 

---

 

개선된 풀이

_ = readLine()
let str = readLine()!.map{ Int($0.asciiValue!) - 96 }
let mod = 1234567891
var (hash, m) = (0, 1)

for i in str {
    hash = (hash + i*m) % mod
    m = (m*31) % mod
}

print(hash)

 

모듈로 연산의 특성덕에

hash값에도 % mod 하고

m값에도 % mod를 하여 계산했습니다.

 

---