BOJ. 15829

#BOJ15829

Hashing

이번 데이터구조 수업 기말고사에 나온 내용이다. 사실 데이터베이스 시스템에서도 이 부분 관련이 나왔는데 시원하게 버렸다. Hashing 부분은 데이터구조의 딕셔너리 부분에서 보았었는데 처음 백준 Class2를 하던 당시에는 자료구조에 대한 기본적인 개념이 부족해서 풀지 못하였던 문제였다. 보통 내가 문제를 해결하는 과정에서 문제가 헷갈리면 가장 많이 사용하는 방법은 문항을 쪼개는 것이다. 해싱이라는 개념 자체는 인지하고 있지만 활용하여서 무언가를 만들어 본적이 없어서 거듭제곱을 어떤 형식으로 구현할지를 먼저 고민하였다. 그 부분이 해결되고 난 이후에 아스키 코드를 이용해서 알파벳 소문자를 숫자로 변경하는 과정을 가졌다. 문항이 만약 알파벳 대문자로 구성되어 있었다면 그 케이스도 나눠줘야 하는 문제였을 것이고, 아마 실버 5문제나 브론즈1 문제가 아니었을까? 문제가 조금 생소하다 보니 신중하게 접근해서 풀었고, 한 번에 정답을 찾을 수 있었다.

# include "iostream"
using namespace std;

int main(void){
    int N, K = 1234567891;
    long long ans = 0, temp = 0;
    string str;
    cin>>N>>str;

    for (int i = 0; i < N; i++){
        temp = str[i] - 'a' + 1;
        for (int j = 0; j < i; j++){
            temp *= 31;
            temp = temp % K;
        }
        ans += temp;
        ans = ans % K;
    }
    cout<<ans;
}