[백준] 15829 Hashing - C++

1. 문제 설명

• 링크 : https://www.acmicpc.net/problem/15829

 문제에서 주어진 해시 함수 식과 주어진 문자열을 바탕으로 해시값을 계산해내는 간단한 문제였습니다!

---

2. 풀이 과정

• 문제 해결의 흐름

1.  우선, 입력 문자열의 각 문자를 정수값으로 변환하는 과정을 거쳤습니다. 처음엔 int(str[i]) - 96과 같은 방식으로 변환하였는데 아래 코드와 같이 변환하는 것이 더욱 깔끔하다고 느껴 바꿨습니다.
2.  이후 pow 함수를 사용하여 해시 함수식을 정확히 계산해 낸 거 같았는데 자꾸 50점에서 그치더라구요 ㅠㅠ.
3.  원인은 2가지로, 입력 크기와 오버플로우 때문이었습니다.
   •  입력 문자열의 길이 L이 최대 50으로 짧아 보였지만, r**i 값은 기하급수적으로 커져 연산 범위를 초과할 가능성이 있었기에 int 자료형보다는 long long 자료형을 사용하여 연산 범위를 늘렸습니다.
   •  M으로 나누는 모듈러 연산을 한 번에 적용하면, 연산 과정에서 값이 너무 커져 long long 범위마저 뛰어넘는 오버플로우 현상이 일어날 수도 있다고 생각되어 중간 값들을 M으로 나누어 항상 M보다 작게 유지하였습니다.

 '1234567891 값이 int 자료형으로도 충분히 담을 수 있으니, 2.만 적용하고 int 자료형 써도 되는거 아닌가?'라는 생각이 들었습니다. 그러나, 연산에는 우선순위가 존재하기에 이전 값들이 이미 int 자료형 연산 범위를 넘어 오버플로우가 발생하였다면 이후 M으로 나누어봤자 문제가 해결되지 않는다는 것을 깨달았습니다!

#include <iostream>
#include <string>

using namespace std;

const int r = 31, M = 1234567891;

int main() {
    // 0. 입력 받기
    int L; // 1 <= L <= 50
    string str;
    cin >> L;
    cin >> str;

    // 1. 주어진 해시함수와 입력 문자열을 사용해 해시값 계산하기
    long long result = 0;
    long long pow = 1;
    for (int i = 0; i < L; ++i) {
        int curVal = str[i] - 'a' + 1;
        result = (result + curVal * pow) % M; // 항상 M보다 작은 값으로 제한
        pow = (pow * r) % M;
    }

    // 2. 출력하기
    cout << result;

    return 0;
}

 

---

3. 후기 

 고등학교 때 변수값 하나하나 전부 설계된 것이고 괜히 주는 것이 아니다는 생각으로 수학 문제를 풀었던 기억이 나는데요! 코테 문제들도 똑같은 거 같네요!