뚝딱뚝딱

***정렬을 이용한 c++ 코드가 필요하다면 아래의 블로그를 참고하세요***

2023.10.18 - [CO-TE/challenge] - [프로그래머스] JAVA / c++ LV2 전화번호 목록 / 해시알고리즘, SORT 풀이 (1)

이번에는 해시 알고리즘을 이용한 java 풀이법을 살펴보겠다.

💡 ''해시 알고리즘''??

해시(hash)는 임의의 데이터를 고정된 길이의 숫자나 문자열로 변환하는 과정이다.

HashMap
- 해시를 사용하는 자료 구조의 일종이다.
- HashMap은 키-값 쌍을 저장하고, 이러한 키-값 쌍에 대한 빠른 검색 및 검색을 지원합니다
- 문자열을 가지고, 해당 문자열이 HashMap에 있는지 바로바로 찾아주기 때문에 O(1)의 복잡도를 갖는다.

HashMap을 활용해서 HashMap에 전화번호 목록들을 키-값 쌍으로 저장하는 과정이 필요하다.

HashMap에 있는 값들은 이제 HashMap에서 지원하는 찾기 함수를 통해서 바로바로 찾아 낼 수 있다.

 java / HashMap 사용 

1. 먼저 HashMap을 Map<>을 통해서 생성하자.

• HashMap의 경우 java.util.HashMap에 정의되어 있으므로 import해준다.
• Map의 경우 java.util.Map에 정의되어 있으므로 import해준다.

import java.util.HashMap;
import java.util.Map;

• HashMap은 Map 인터페이스를 구현한 클래스로, Map<>의 객체에 HashMap의 생성자로 생성되도록 할 수 있다.
• 전화번호의 경우 String문자열로 되어 있기 때문에, <String, Integer>를 키-값 쌍으로 갖는 Map을 생성한다.
• 사실상 Integer(값)는 쓸 일이 없고, Map을 활용하기 위한 것이므로, 인덱스를 넣어주겠다.

Map<String, Integer> map = new HashMap<>();

2. HashMap에 phone_book에 있는 값들을 키로, 그리고 인덱스를 값으로 넣어준다.

for(int i=0; i<phone_book.length; i++){
            map.put(phone_book[i], i);
        }

• 여기서 주의할 점..phone_book의 배열 크기는 .length로 얻어 올 수 있다. (c++의 size()와 헷갈리지 말자)
• map에 요소를 넣을 때는 put을 사용하고, 지정해준 키-값 쌍을 인자로 넣어주면 된다.

3. 2중 for문을 통해서 phone_book에 있는 전화번호 각각의 접두어가 HashMap에 있는지를 확인한다.

for(int i=0; i<phone_book.length; i++){
            for(int j=0; j<phone_book[i].length(); j++){
                if(map.containsKey(phone_book[i].substring(0,j))){
                    return false;
                }

• 현재 가리키는 전화번호의 0부터 j번 까지의 문자열이 HashMap의 키를 통해 검색한 결과에 있으면, j번까지의 접두어로 존재하는 전화번호가 있다는 의미이기 때문에, false를 반환하도록 한다.
• 이때 사용하는 map의 함수가 containsKey()로, 검색하고자 하는 값을 인자로 넣어주면 된다.
• 자바에서 String의 substring()함수는 자르고자 하는 문자열의 시작 인덱스와 끝인덱스를 인자로 넣어주고, 만약 인자를 하나만 적는다면 해당 시작부터 끝까지 잘라준다.
• string의 쓰임같은 경우 c++에서와 헷갈리지 않도록 주의한다!!!
• 참고로 문자열의 길이를 반환할 때는 .length()이다! 

이렇게 해시를 이용하면 바로바로 문자열을 map의 함수를 통해 검색할 수 있으므로 효율성에서 높아진다.

전체코드는 아래와 같다.

//해시로 풀이
import java.util.HashMap;
import java.util.Map;

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        
        Map<String, Integer> map = new HashMap<>();
        
        for(int i=0; i<phone_book.length; i++){
            map.put(phone_book[i], i);
        }
        
        for(int i=0; i<phone_book.length; i++){
            for(int j=0; j<phone_book[i].length(); j++){
                if(map.containsKey(phone_book[i].substring(0,j))){
                    return false;
                }
                    //substring은 start index부터 end index까지
                    //java에서는 string size가 아니고 배열 크기는 length, 배열 안에서 문자열                        길이는 length() 
            }
        }
        
        
        return answer;
    }
}