[백준 15829번 node.js] Hashing

Jessie H·2022년 6월 24일

15829 Hashing node.js 백준 해시

알고리즘 공부

목록 보기

13/20

This banner made by here

문제 링크

풀이

<script>
//첫 두 줄에 입력값을 받는다
const input = require("fs").readFileSync("/dev/stdin").toString().trim().split("\n");
//l은 첫번째로 받는 입력 값, 문자열의 길이, 길이는 음수가 될 수 없으므로 +를 붙여준다
const l = +input[0]
//string는 두번째로 받는 입력 값(문자열)
const string = input[1];

function hashFunc() {  
  const M = 1234567891;
  //hash에 몰아서 출력시킬 것이기 때문에 누적값 처리를 위해 0으로 설정
  let hash = 0;
  //r은 31의 제곱으로 점점 커질 것이므로 처음에는 31^0에 해당하는 1을 설정한다.
  let r = 1;

  //여기서부터는 문제에 나와있는 시그마를 활용한 식을 거의 옮긴 것이나 다름없다
  for (let i = 0; i < a.length; i++) {
    hash += (string[i].charCodeAt() - "a".charCodeAt() + 1) * r;
    //처음 31^0 곱해주고 난 후 31씩 계속 제곱 만들어줘야 하기 때문에 r에 계속 31씩 곱해준다
    r *= 31;
    //r이 M보다 커지는 것을 막기 위해 r을 곱해준다음 나눈 나머지로 r을 바꿔준다
    r %= M;
    //문제에 나와있는 해싱함수 식에서 마지막에 시그마 다해준 후 M으로 나눈 나머지를 hash로 두라고 했기 때문에 
    //hash를 M으로 나눈 나머지를 hash에 저장한다.
    hash %= M;
  }

  return hash;
}

console.log(hashFunc());
</script>

참고:
https://ryulurala.tistory.com/275
https://github.com/xCrypt0r/Baekjoon/blob/master/src/15/15829.js

문제 풀이 포인트

문제 풀이 중 hash += (string[i].charCodeAt() - "a".charCodeAt() + 1) * r;에서
string[i].charCodeAt() - "a".charCodeAt() + 1하는 이유가 이해가 안가서 풀기 어려웠다.

이렇게 해야하는 이유는 예시를 보면 알 수 있다.

string = "abcde"인 경우

a = "abcde"인 경우 출력값은 12345가 되어야한다.
문자열"a"를 정수로 변환하는 방법 중 하나로 UTF-16 코드로 변환하는 방법이 있다.
"a".charCodeAt() = 97
여기서 문자열 첫번째 문자인 "a"를 정수로 변환시킨 값이 1이 되도록 하려면??
-"a".charCodeAt()해서 값을 0으로 만들고 다시 1을 더하면
"a"를 정수로 변환시킨 값은 1이 된다. -> 첫번째 문자는 1로 바뀜
이제 abcde 중 b를 정수로 변환시킨다면??

"b".charCodeAt() = 98이 되므로 98 - 97 + 1 = 2가 된다. -> 두번째 문자는 2로 바뀜

이런 방식으로 'abcde'를 바꾸면 12345가 되기 때문에 이것을 식으로 바꾸면

<script>
for (let i = 0; i < l; i++) {
	hash += string[i].charCodeAt() - "a".charCodeAt() + 1
    //...이하 생략
}
</script>

이렇게 식을 바꿀 수 있다

새로 알게 된 문법

Math.floor()

소수점을 버림하여 정수 반환

Math.random()

0 ~ 0.999... 사이의 값 반환

Math.floor(Math.random() * N) + 1

Math.random() * N : 0 ~ 0.999 사이의 값 정수 N = 0 ~ (N-1).999 사이의 값 반환
```Math.floor(Math.random() N): 0 ~ N-1 사이의 정수 반환Math.floor(Math.random() * N) + 1``` : 1부터 N 사이의 정수 반환