[BOJ] 백준 15829 Hashing (Swift)

문제

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

15829번: Hashing

풀이

문제와 힌트를 보면 쉽게 풀 수 있는 문제라고 생각할 수 있다.
하지만 문자열의 길이가 최대 50이다. 이는 $31^49$를 구해주어야 한다. Swift에서는 Big Integer를 지원하지 않는데 어떻게 풀이할 수 있을까?

먼저 모듈러 연산에 대해 이해하고 있어야 한다.

• $(a + b) \mod M = ((a \mod M) + (b \mod M)) \mod M$
• $(a - b) \mod M = ((a \mod M) - (b \mod M)) \mod M$
• $(a \times b) \mod M = ((a \mod M) \times (b \mod M)) \mod M$

의 성질을 알아야 한다.

이는 다른 블로그나 위키에 잘 정리된 문서가 많아서 패스하고..
이를 알면 나누어야 할 값이 1234567891 이라는 것을 알기 때문에 오버플로우 문제를 피할 수 있다.

마지막으로 a, b, c 와 같은 소문자 알파벳을 1, 2, 3과 같은 정수형으로 치환해주어야 한다.
Character 자료형의 asciiValue 프로퍼티로 구할 수 있다.
a의 ascii 값은 97이므로, a를 1로 치환하기 위해서는 a.asciiValue - 96을 해주면 된다.
나머지 알파벳들도 아스키 값이 1씩 증가하는 형태이므로, 고차함수 map을 사용해 입력받은 문자열을 정수형의 배열로 치환해주었다.

소스코드

	let M = 1_234_567_891
	let l = Int(readLine()!)!
	let array = readLine()!.map { Int($0.asciiValue!) - 96 }
	var answer = 0
	func pow31(_ r: Int) -> Int {
	var answer = 1
	for _ in 0..<r {
	answer *= 31
	answer %= M
	}
	return answer % M
	}
	for i in 0..<l {
	answer += array[i] * pow31(i)
	answer %= M
	}
	print(answer % M)

view raw Hashing.swift hosted with ❤ by GitHub

후기

BigInt를 지원하는 언어였다면 더 쉽게 풀 수 있는 문제였다.
지원을 안한다면 모듈러 연산에 대한 이해가 있어야 한다.