[알고리즘]문자열 집합

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.text.MessageFormat;
import java.util.HashSet;
import java.util.Objects;
import java.util.Set;
import java.util.StringTokenizer;

/* **
 * 터렛
 *
 *
 *
 **/
public class Main {
    public static void main(String[] args) {
        try (
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        ) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());
            // 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다.
            if (!(1 <= n && n <= 10000 && 1 <= m && m <= 10000)) {
                String errorMessage = MessageFormat.format("n =>{0}, m =>{1} 는 1 이상 10,000 이하여야 합니다.", n, m);
                throw new IllegalArgumentException(errorMessage);
            }
            Set<Word> words = new HashSet<>();
            for (int i = 0; i < n; i++) {
                String inputWord = br.readLine();
                Word savedWord = new Word(inputWord);
                words.add(savedWord);
            }
            int answer = 0;
            for (int i = 0; i < m; i++) {
                String targetWord = br.readLine();
                Word target = new Word(targetWord);
                if (words.contains(target)) {
                    answer++;
                }
            }
            System.out.println(answer);
            
            
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
    
    public static class Word {
        
        private final String value;
        
        public Word(String value) {
            Objects.requireNonNull(value);
            
            if (!(value.length() <= 500)) {
                String errorMessage = MessageFormat.format("value 는 500자 이하여야 합니다. value: {0}", value);
                throw new IllegalArgumentException(errorMessage);
            }
            for (char c : value.toCharArray()) {
                if (!('a' <= c && c <= 'z')) {
                    String errorMessage = MessageFormat.format("value 는 소문자만 가능합니다. value: {0}", value);
                    throw new IllegalArgumentException(errorMessage);
                }
            }
            
            this.value = value;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (!(o instanceof Word)) return false;
            
            Word word = (Word) o;
            
            return value.equals(word.value);
        }
        
        @Override
        public int hashCode() {
            return value.hashCode();
        }
        
        @Override
        public String toString() {
            return "Alphabet{" +
                "value=" + value +
                "}\n";
        }
    }
    
    
}

깨달은 점

• HashSet() 의 contains() 는 어떻게 상수시간에 값의 존재여부를 알 수 있는 걸까?
  • 해시셋은 해시맵과 아주 유사하게 동작합니다.

  해시맵 의 동작

  • 키 - 값 쌍을 저장하는데 사용되는 데이터 구조
  • 키는 고유한 값을 가져야하며
  • 내부적으로 버킷 이라는 배열을 사용하여 데이터를 저장합니다.
  • 키는 해시함수를 통해 ⇒ 해시코드로 변환되며, 해당 값을 통해 버킷의 인덱스 를 결정하게 됩니다.

  상수시간에서의 contains

  • HashSet 의 contains 는 내부적으로 HashMap 의 get() 메서드를 호출합니다.
  • HashSet 은 HashMap 의 get 호출로 해당 값과 내가 넣으려는 값이 같는지 체크하고 값이 같다면 true 를 반환하겠죠
  • 그러면 get으로 어떻게 값을 찾아오는걸까요?
    • 검색하려는 객체의 hashcode 를 계산하여 해당 버킷의 위치를 찾아낼 수 있습니다.
    • 그 버킷에 담긴 값이 하나라면 무조건 상수시간에 값을 가져올 수 있겠죠

  항상 상수시간을 보장하냐?

  • 해시 충돌이 발생하는 경우 상수 시간을 보장하지 않습니다
    • 버킷의 초기 용량이 부족한 경우
    • 여러 키가 동일한 해시코드를 가질 수도 있습니다.
    • 버킷은 내부적으로 연결 리스트 또는 트리 구조로 데이터가 저장되는데,
    • 해시코드가 동일한 경우 버킷 내부에 계속적으로 배열 형식으로 담기게됩니다.
    • 만약 특정 버킷을 탐색하였는데 배열을 탐색해야한다면, 최악의 경우 O(n) (하나의 버킷에만 존재하는 경우) 의 성능으로 하락하게됩니다.

Uploaded by N2T