99클럽 코테 스터디 7일차 TIL + Hashing

오늘의 학습 키워드 및 문제

#해시 #모듈러연산
백준_브론즈2_Hashing

문제풀이

정.말.쉽.지.않.았.다.
삽.질.도.많.이.했.고.이.해.하.는.데.에.오.래.걸.렸.다.

첫번째 도전 (틀렸습니다)

아래 코드 볼 필요도 없다.
이번 주차 주제가 해시니까 해시로 풀면 되겠지~ 하고 해시로 풀었다.
문자열의 각 문자를 key로 지정하고 그에 해당되는 계산 값을 value에 저장하고 반복문으로 value들을 더하려고 했다.
그런데 map은 key를 중복할 수 없기 때문에 연속으로 같은 문자를 가지는 예제 2번에 벗어난다.
그리고 BufferedWriter는 문자열로 반환하기 때문에 int를 String으로 변환해주는 과정이 필요하다.

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        HashMap<Character, Integer> map = new HashMap<>();
        int rtn = 0;
        
        // 문자열의 길이
        int l = Integer.parseInt(br.readLine());
        // 길이만큼 입력된 문자열
        String s = br.readLine();
        
        // 해시맵 저장
        for(int i=0; i<l; i++) {
            // 소문자 a의 아스키 값은 97
            map.put(s.charAt(i), s.charAt(i)-96);
        }
        
        // map 반복문으로 계산하여 각 문자의 계산 결과를 map에 저장
        for(Map.Entry<Character, Integer> m : map.entrySet()) {
            map.put(m.getKey(), m.getValue() * (int)Math.pow(31, m.getValue()-1));
        }
        
        // map 반복문으로 더하기
        for(Map.Entry<Character, Integer> m : map.entrySet()) {
            rtn += m.getValue();
        }
        
        bw.write(rtn);
        bw.flush();
        bw.close();
        br.close();
    }
}

두번째 도전 (50점)

첫번째 도전에서 실패한 테스트 케이스가 있기에 해시로 푸는 것은 아닌 것 같다고 생각했다.
그러면 그냥 계산한 값을 더하면 되겠구나 생각했다.

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int rtn = 0;
        
        // 문자열의 길이
        int l = Integer.parseInt(br.readLine());
        // 길이만큼 입력된 문자열
        String s = br.readLine();
        
        // 해시 값 저장
        for(int i=0; i<l; i++) {
            // 소문자 a의 아스키 값은 97 (97-96=1)
            int charToInt = s.charAt(i)-96;
            rtn += charToInt * Math.pow(31, i);
        }
        
        bw.write(String.valueOf(rtn));
        bw.flush();
        bw.close();
        br.close();
    }
}

세번째 도전 (50점)

이리저리 해도 계속 50점이라서 문제에 나와있는 것을 모두 활용해야 되는구나 생각했다.
(각 문자 * 31^각 문자-1) 계산한 후 mod M 적용하는 것이라 생각했다.

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        final int r = 31;
        final int disjoint = 1234567891;
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int squared = 1; // 제곱 계산 변수
        int rtn = 0; // 결과 저장 변수
        
        // 문자열의 길이
        int l = Integer.parseInt(br.readLine());
        // 길이만큼 입력된 문자열
        String s = br.readLine();
        
        // 해시 값 저장
        for(int i=0; i<l; i++) {
            // 소문자 a의 아스키 값은 97 (97-96=1)
            int charToInt = s.charAt(i)-96;
            rtn += (charToInt * squared) % disjoint;
            // 다음 제곱값 계산
            squared *= r;
        }
        
        bw.write(String.valueOf(rtn));
        bw.flush();
        bw.close();
        br.close();
    }
}

네번째 도전 (100점 근데 이제 chatGPT를 곁들인..)

세번째도 50점? 나 100점 받고 싶은데?!
결국 chatGPT의 도움을 받았다.
모듈러 연산에 대한 개념과 해시 함수와 모듈러 연산의 관계을 잘 알아야 풀 수 있는 문제였다.

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        final int r = 31;
        final int disjoint = 1234567891;
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        long squared = 1; // 제곱 계산 변수
        long rtn = 0; // 결과 저장 변수
        
        // 문자열의 길이
        int l = Integer.parseInt(br.readLine());
        // 길이만큼 입력된 문자열
        String s = br.readLine();
        
        // 해시 값 저장
        for(int i=0; i<l; i++) {
            // 소문자 a의 아스키 값은 97 (97-96=1)
            int charToInt = s.charAt(i)-96;
            rtn = (rtn + (charToInt * squared) % disjoint) % disjoint;
            // 다음 제곱값 계산
            squared = (squared * r) % disjoint;
        }
        
        bw.write(String.valueOf(rtn));
        bw.flush();
        bw.close();
        br.close();
    }
}

다섯번째 도전 (100점 근데 이제 아래의 공부 내용을 곁들인..)

내가 생각하는 수식의 내용은 이러했다.

• a의 i번째와 r에 i-1만큼 제곱한 것을 곱한 값을 모듈러 연산
• 곱한 값들을 합할 때마다 모듈러 연산

내용 복습 겸 아래의 모듈러 연산에 대해 공부한 내용 중 덧셈, 곱셈 부분을 적용하여 다시 풀어봤다.
그래봤자 모듈러 연산 부분 코드 조금 바뀐 거지만..

chatGPT가 준 코드를 봤을 때 그냥 무지성 모듈러 연산 한거 아닌가 했는데 알고 보니 이유가 있었던 것 같다.
rtn과 charToInt는 숫자가 범위 안에 속하니 모듈러 연산을 일부러 안해준 것 같다.

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        final int r = 31;
        final int disjoint = 1234567891;
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        long squared = 1; // 제곱 계산 변수
        long rtn = 0; // 결과 저장 변수
        
        // 문자열의 길이
        int l = Integer.parseInt(br.readLine());
        // 길이만큼 입력된 문자열
        String s = br.readLine();
        
        // 해시 값 저장
        for(int i=0; i<l; i++) {
            // 소문자 a의 아스키 값은 97 (97-96=1)
            int charToInt = s.charAt(i)-96;
            rtn = (rtn % disjoint + ((charToInt % disjoint) * squared) % disjoint) % disjoint;
            // 다음 제곱값 계산
            squared = (squared * r) % disjoint;
        }
        
        bw.write(String.valueOf(rtn));
        bw.flush();
        bw.close();
        br.close();
    }
}

공부한 내용정리

• BufferedWriter는 문자열로 반환하기 때문에 int를 String으로 변환해주는 과정이 필요
• 'a' ascii value = 97
• Math.pow(a,b) 는 거듭제곱 계산 수행 (a: 값, b: 제곱할 횟수) 리턴타입은 double

---

모듈러 연산(modular arithmetic)

✒️ 모듈러 연산이 뭔가요?

모듈러 연산의 개념

• 숫자를 특정 정수로 나눈 나머지를 계산하는 연산 => 나머지 연산

모듈러 연산의 표현

보통 a mod n 또는 a%n 으로 표현
결과는 a를 n으로 나눈 나머지

• a : 나눌 숫자
• n : 나누는 숫자

모듈러 연산의 특징

• 항등성
  • 만약 a < n 이라면 a mod n = a
• 주기성
  • 모듈러 연산의 결과는 0부터 n-1 사이의 값을 가짐
• 덧셈, 뺄셈, 곱셈
  • (a+b) mod n = ((a mod n) + (b mod n)) mod n
  • (a-b) mod n = ((a mod n) - (b mod n) + n) mod n
  • (a*b) mod n = ((a mod n) x (b mod n)) mod n

✒️ 해시 함수를 구현할 때 모듈러 연산이 왜 필요한가요?

테이블 크기 내에 데이터 매핑

해시 함수는 입력 값을 어떠한 숫자로 변환
해시 테이블의 크기가 N이라고 할 때 (입력값 mod N) 을 계산하면 해시값이 항상 0부터 N-1 사이의 값으로 유지
해시 테이블의 배열 인덱스를 초과하지 않도록 보장

고른 데이터 분포

모듈러 연산은 키를 테이블 크기 내에 균일하게 분산시킴
즉 입력값들이 특정 영역에 몰리지 않도록 해줌

• 123 mod 10 = 3
• 456 mod 10 = 6
• 789 mod 10 = 9

충돌 관리

해시 함수는 두 입력값이 동일한 해시값을 갖는 경우가 발생할 수 있음
모듈러 연산을 사용하면 충돌의 분포가 예측 가능해지고 충돌 처리(체이닝, 선형 탐색)가 쉬워짐

계산 효율성

모듈러 연산은 해시 함수의 계산 속도를 저하시키지 않음
간단한 수학 연산이기 때문