[Programmers] Hash - 전화번호 목록

1. 나의 풀이

1. 전화번호를 정렬한다.
2. 정렬한 배열의 인덱스 0부터 정한 기준점에서 그 뒤의 string변수의 시작이 기준점 string 변수인지 확인한다.

2-1. 풀이

1번 풀이

import java.util.Arrays;

class Solution {
    public boolean solution(String[] phone_book) {
        Arrays.sort(phone_book);
        boolean answer = true;
        
        int j = 1;
        for(String num: phone_book){
            for(int i=j; i<phone_book.length; i++){
                if (phone_book[i].startsWith(num)){
                    answer = false;
                }
            }
            j++;
        }
        return answer;
    }
}

효율성 문제,, 2중 for문을 이용하다보니 효율성이 굉장히 떨어진다.

---

2번 풀이

import java.util.Arrays;

class Solution {
    public boolean solution(String[] phone_book) {
        Arrays.sort(phone_book);
        boolean answer = true;
        for(int i=0; i<phone_book.length-1; i++){
            if (phone_book[i+1].startsWith(phone_book[i])){
                answer = false;
            }
        }
        return answer;
    }
}

정렬을 통해서 i번 인덱스와 i+1번 인덱스만을 비교하게 한다.
int 배열이 아니라 string배열이기 때문에 오름차순 정렬이 아니라 앞자리가 비슷한대로 정렬함
String[] arr = {"12", "5", "789", "1234"} -> String[] arr2 = {"12", "1234", "5", "789"}

---

3번 풀이

그래도 Hash 문제인데,,, 해쉬로 풀어보자.

import java.util.HashMap;

class Solution {
    public boolean solution(String[] phone_book) {
        HashMap<String, Integer> map = new HashMap<>();
        int i = 0;
        for(String temp: phone_book){
            map.put(temp, i);
            i++;
        }
        
        for(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;
                }
            }
        }
        return true;
    }
}

HashMap형 변수를 생성 후 키 값으로 전화번호를 넣는다.
pphone_book 배열에서 문자열을 하나 씩 꺼내서, 1문자, 2문자,,, 계속 늘려가면서 쪼개서 해당 쪼갠 문자열이 HashMap 배열의 key로 들어가 있는지 확인한다.

---

3. 메서드

String.startsWith(String temp) temp 문자열로 String의 시작하는지 확인한다.
String.substring(i, j) 문자열을 i번 인덱스에서 부터 j-1 인덱스까지 자른다.
Map.containsKey(String temp) temp 문자열이 Map의 키값으로 들어가 있는지 확인한다.