Hashing_백준15829

 

<문제>

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

 

<풀이>

import sys

input = sys.stdin.read().splitlines()

def solve(input):
    L = int(input[0])
    string = input[1]

    dict = {}
    temp_list = ['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']

    sum = 0

    for i, char in enumerate(temp_list):
        dict[char] = i+1

    for i, char in enumerate(string):
        sum += dict[char] * 31**i

    return sum % 1234567891

print(solve(input))

 

- 알파벳과 숫자를 묶은 딕셔너리 준비

- 전체 sum에다 1234567891를 나눈 나머지를 구하면 됨

 

 

<node 풀이>

const fs = require("fs");
const [L, str] = (
  process.platform === "linux"
    ? fs.readFileSync("/dev/stdin").toString()
    : `5
zzzzzzz`
)
  .trim()
  .split('\n')

const l = Number(L)
const arr = str.split('')

const aMap = {
  'a': 1,
  'b': 2,
  'c': 3,
  'd': 4,
  'e': 5,
  'f': 6,
  'g': 7,
  'h': 8,
  'i': 9,
  'j': 10,
  'k': 11,
  'l': 12,
  'm': 13,
  'n': 14,
  'o': 15,
  'p': 16,
  'q': 17,
  'r': 18,
  's': 19,
  't': 20,
  'u': 21,
  'v': 22,
  'w': 23,
  'x': 24,
  'y': 25,
  'z': 26
};

let hash = 0;
let r = 1
for (let i = 0; i < arr.length; i++) {
  hash += aMap[arr[i]] * r
  hash %= 1234567891
  r *= 31
  r %= 1234567891
}

console.log(hash)

 

- 자바스크립트의 Number 타입은 64비트 부동소수점 형식 사용, 2^53-1을 넘어가는 정수는 오차 발생가능성 있음

- 그래서 BigInt 타입을 이용하던지

- 아님 계산을 쪼개서 나누던지 (중간에 모듈러 연산)