백준 15829번 [Hashing](C++)-yes6686- 티스토리

백준 문제 풀이: 15829 [Hashing]

---

문제 링크: https://www.acmicpc.net/problem/15829

문제 설명:

주어진 문자열을 특정 규칙에 따라 해싱하여 정수값으로 변환하는 문제입니다. 각 문자는 a=1, b=2, ..., z=26의 값으로 매핑되며, 각 자리의 값은 31의 거듭제곱에 해당하는 가중치를 곱한 뒤 모듈러 연산을 통해 결과를 구합니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);    

    int n;
    cin >> n;
    string s;
    char c;
    for (int i = 0; i < n; i++) {
        cin >> c;
        s.push_back(c);
    }

    long long int sum = 0;
    long long int k = 1;

    for (int i = 0; i < n; i++) {
        sum = (sum + (s[i] - 96) * k) % 1234567891;
        k = (k * 31) % 1234567891;
    }

    cout << sum;
}

---

코드 설명

• 핵심 알고리즘: 주어진 문자열에 대해 각 문자에 가중치를 곱한 뒤 모듈러 연산을 적용하여 해싱 값 계산
• 구현 세부사항:
  • 각 문자는 a=1, b=2, ..., z=26으로 매핑됩니다.
  • 각 자리의 값은 31의 거듭제곱에 해당하는 가중치를 곱합니다.
  • 중간 결과와 최종 결과에 대해 모듈러 연산을 적용하여 오버플로를 방지합니다.
• 시간 복잡도: O(n)
  • 문자열의 길이가 n일 때, 한 번의 순회로 해싱 값을 계산

---

결과

주어진 문자열에 대해 특정 규칙에 따라 해싱 값을 계산하고, 모듈러 연산으로 결과를 출력합니다. 간결하고 효율적인 코드로 문제를 해결했습니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!