99클럽 코테 스터디 1일차 TIL - 해시

오늘의 학습 키워드

해시

---

알고리즘 문제

• 프로그래머스 Level 2 - 전화번호 목록
• https://school.programmers.co.kr/learn/courses/30/lessons/42577

---

공부한 내용

Hash(해시)

• 특징
  • 동일한 입력 값에 대해 항상 동일한 출력 값이 보장된다.
  • 출력 데이터 값으로 입력 데이터 값을 알 수 있다.
  • 해싱: 입력 값(Key)을 해시함수에 넣어 출력 값을 HashCode에 매핑하는 것.
  • 해싱을 통해 만든 해시코드를 인덱스로 사용해서 해시를 활용한 자료구조의 검색이 빠르다. [O(1)]

Hashing(해싱)

• HashSet에 저장되는 객체는 해시 함수를 통해 고유한 해시 코드 (hash code)로 변환한다.
• 객체의 해시 코드가 배열의 인덱스로 변환되어 해당 위치에 객체가 저장된다.

HashSet

• 순서를 파악하지 않고, 중복된 데이터를 제거하거나 이미 데이터가 추가되었는지 검사할 때 주로 사용한다.
• 내부적으로 해시 테이블(Hash Table)을 사용해서 해시 코드를 통해 직접 접근하기 때문에 검색이 빠르다.
  
  • Hash Table : 해시 테이블은 배열 형태로, 검색하고자 하는 객체의 해시 코드를 계산하여 해당 해시 코드에 매핑되는 버킷을 찾는다. (버킷은 각 배열의 요소)

---

오늘의 회고

처음 시도

• 처음에는 단순 문자열로 substring()을 사용해서 구현했는데 순서가 있는데다가 정렬을 하지 않아서 ["234", "23"] 인 경우 에러가 났고, 통과한다 해도 이중 for문으로 아마 효율성 테스트에서도 통과를 못했을 것이다.

해결

• HashSet을 사용해서 중복을 제거하고, 순서를 고려하지 않도록 했다. 문자열 자르기로 문자열을 비교하고 싶어서 substring()으로 for문을 돌면서 하나씩 늘려가면서 자르면서 Set과 비교했다.
• 만약 문자열이 전체 포함을 비교하고 싶다면 Arrays.sort()로 정렬 후에 startsWith() 또는 contains()로 앞뒤 요소를 비교하면 된다.

---

문제 풀이

HashSet.contains()

• HashSet 사용: 중복된 문자열 제거해서 set에 저장해서 비교
• HashSet 사용 이유: 해시 함수를 적용해서 계산한 해시 코드로 키를 배열에 저장한다.
• 시간복잡도: O(1)
• github 풀이

Algorithm-Practice/프로그래머스/2/42577. 전화번호 목록/전화번호 목록.java at main · dev-jinius/Algorith

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {

        Set<String> set = new HashSet<>();
        for (String num : phone_book) {
            set.add(num);
        }

        for (String num : phone_book) {
            for (int i = 1; i < num.length(); i++) {
                if (set.contains(num.substring(0, i))) {
                    System.out.println("here [" + num.substring(0, i) + "]");
                    return false;
                }
            }
        }

        return true;
    }
}

다른 풀이

Arrays.sort()

• 정렬 사용: Arrays.sort()를 사용해서 오름차순으로 정렬.
• 정렬 사용 이유: prefix 비교이기 때문에 정렬 후 앞뒤 요소만 비교하기 위해서.
• 시간복잡도: O(NlogN)

import java.util.Arrays;

class Solution {
    public boolean solution(String[] phone_book) {
        Arrays.sort(phone_book);

        for (int i = 0; i < phone_book.length-1; i++) {
            if (phone_book[i+1].contains(phone_book[i])) {
                return false;
            }
        }

        return true;
    }
}