[프로그래머스] 해시 Level 2. 전화번호 목록 (JAVA)

n+(n-1)+(n-2)+...+1 해서 n^2 나오나 했는데, 생각해보니까 정렬해서 바로 아래 값이랑만 비교하면 되겠더라고.

가나다

가나다라마바사

가나라

이런식으로 정렬될꺼아냐?

시간복잡도는 정렬시간인 nlogn으로 나올것같다.

그래서 풀기는 금방 풀었는데...

 

코드

import java.util.*;
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].startsWith(phone_book[i])){
                return false;
            }
        }
        return true;
    }
}

결과

 

---

근데 해시 문제잖아?

해시로 풀어야될거같은데 아무리 생각해도 모르겠어서 다른 사람 풀이를 찾아봤다.

 

코드

import java.util.HashMap;

class Solution {
    public boolean solution(String[] phone_book) {
        HashMap<String, Integer> hashMap = new HashMap<String,Integer>();
        for(String phone : phone_book){
            hashMap.put(phone, 1);
        }
        for(String phone : phone_book){
            for(int idx=0; idx<phone.length(); idx++){
                if(hashMap.containsKey(phone.substring(0,idx))){
                    return false;
                }
            }
        }
        return true;
    }
}

결과

 

2중 for문이긴하지만 두번째 for문은 phone_book이 아니라 각 전화번호 길이 만큼만 돈다!

이러면 두번째 for문은 최대길이 20밖에 안되니까 상수취급해서 시간복잡도 n이라고 해도 되지않을까...?? 

hash를 사용한 여러가지 풀이가 있었지만 이게 제일 맞는거같다.

(대부분은 나처럼 sort 썼더라...)