[BaekJoon 15829][🟤2] Hashing

❓ 문제

백준 15829 - “Hashing”

🎯 난이도

Bronze 🟤2

🧠 풀이

1. 내 풀이 (해싱)

- 알고리즘

• string, Hashing

- 설명

자료형과 Modular 연산을 잘 생각해가며 풀어야 하는 문제이다.

간단해 보이지만 의외로 하나만 잘못 써도 부분 점수 밖에 얻지 못하는 경우가 발생한다. 특히나 곱해지는 값이 31의 거듭제곱으로 계속해서 더해지기 때문에, 순식간에 long long의 범위를 넘으므로, '자료형'과 'Modular 연산'의 특징을 잘 생각해서 풀어야 완전히 통과할 수 있다.

- 코드

내 풀이 코드

#include <iostream>

#include <string>

#include <cmath>


using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    constexpr int iR{ 31 };
    constexpr int iM{ 1234567891 };

    int iL{};
    string strInput{};

    cin >> iL >> strInput;

    // int 범위를 넘을 수 있으므로 long long 자료형 사용
    long long iSum{};
    long long iPower{ 1 };
    for(int i = 0; i < iL; ++i)
    {
        long long llVal{ strInput[i] - 'a' + 1};

        // llVal <= 26, iPower < iM 이므로 long long의 범위를 넘지 않는다
        // 따라서 나머지 연산의 분배 법칙은 안 써도 됨
        iSum = (iSum + llVal * iPower) % iM;
        iPower = (iPower * iR) % iM;
    }

    cout << iSum;

    return 0;
}

---

💭 후기

쉬워 보이지만 생각보다 자료형의 범위와 Modular 연산에 대해 제대로 파악하지 않으면 부분 점수만 계속 맞게 된다. 나 또한 그랬다. 기본적인 지식을 제대로 알아두자.