[Algorithm] Swift 백준 15829번

 

 

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

15829번: Hashing

 

문제접근 

 

브론즈 문제라 쉽게 생각함... 문제만 길고 사실 구현할 것도 많이 없었는데 ~~ 

입력받은 하나의 문자열을 -> 수열로 변경하는 부분에서 막혔음... 아스키코드는 생각도 못함 

결국 다른 분 코드를 참고했음.. 

 

정답풀이

 

우선 참고한 코드를 보자!!

 

import Foundation

let mod = 1234567891
let n = Int(readLine()!)!
let input = Array(readLine()!).map { Int(exactly: $0.asciiValue!)! - 96}
var hash = 0
var m = 1
for i in input {
    hash = (hash + i*m) % mod
    m = (m*31) % mod
}
print(hash)

 

let input = Array(readLine()!).map { Int(exactly: $0.asciiValue!)! - 96}

 

위 코드가 내가 막힌  문자열을 -> 수열로 변경하는 부분임 

 

우선 입력받은 값을 배열에 넣어줌

 

그 후 배열의 첫 번째 값부터 접근해 그 값을 아스키코드로 변환해 줌 

 

 

asciiValue는 공식문서에 따르면 ASCII 문자인 경우 이 문자의 ASCII 인코딩 값이라 함 

 

 

exactly: 는 공식문서에 따르면 정확하게 표현할 수 있는 경우 주어진 부동 소수점 값에서 정수를 생성한다고 함.

 

let input = Array(readLine()!).map { $0.asciiValue}
// [Optional(97)]

 

아스키코드로 변경하면 Optional()로 쌓여서 나오는데

 

우리는 수열로 변경해주어야 하기 때문에 

 

Int로 변경해야 함!! 

 

 

그때 exactly: 를 사용해야 한다고 함!!! 

 

사용 안 하면 에러 나긴 함.. 

 

그냥 ASCII 값으로부터 정수로 만들어줘야 하기 때문인 거 같음... 문제도 보면 정수로 치환한다고 되어있긴 함.. 

 

그리고! 

 

그 후 96을 빼주어야 함!!! 

 

왜냐?? 

 

문제를 보면 문자열에는 영문 소문자(a, b,..., z)로만 구성되어 있다고 가정하자. ~~ 라고함.

 

 

아스키코드 표를 보면 영문 소문자(a, b,..., z)는 97부터 ~ 122까지임 

 

입력으로 a를 넣어보면

 

let input = Array(readLine()!).map { Int(exactly: $0.asciiValue!)!}
// 97

 

97이 나오는데 우리는 a가 1, b가 2...  이렇게 나아가야 하기 때문에 

 

96을 빼주게 되는 거임!! 

 

이렇게 하면 'a'는 1, 'b'는 2,..., 'z'는 26으로 매핑됨!!! 

 

아래 코드를 보자 

 

var hash = 0
var m = 1
for i in input {
    hash = (hash + i*m) % mod
    m = (m*31) % mod
}
print(hash)

 

 zzz 가 입력으로 들어갔다고 하면 -> 262626 임

 

 

위와 같이 hash 값을 증가시키고 있음 

 

여기서 m값에 mod를 계속 나눠주는 이유가 궁금했는데!  🤔

 

문제에 보면 유한한 범위의 출력을 가져야 한다고 했으니까 적당히 큰 수 mod으로 나눠줘야 하는데   

 

그래서!! hash 값이 너무 커지는 것을 방지하기 위해서 m값도 mod로 나눠주는 거 같음 

 

안 해주면 부분적으로만 맞음!! 

 

 

처음에 위코드가 복잡해 보여서 

 

import Foundation

let mod = 1234567891
let n = Int(readLine()!)!
let input = Array(readLine()!).map { Int(exactly: $0.asciiValue!)! - 96}
var hash = 0
var m = 0
for i in input {
    hash += i*Int(pow(31.0, Double(m))) % mod
    m += 1
}
print(hash)

 

이렇게 바꿔봤는데 

 

 

50점밖에 안 나옴 

 

부분적으로만 맞은 거 같음.. 

 

 

asciiValue와 exactly:를 새롭게 알게 됨!!  

 

 

 

 

 

 

참고 및 인용

 

https://velog.io/@baekteun/%EB% B0% B1% EC% A4%80-15829-Hashing-Swift