[프로그래머스 레벨2] 전화번호 목록 : HashSet사용(Java)

문제

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

• 구조대 : 119
• 박준영 : 97 674 223
• 지영석 : 11 9552 4421

전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

 

제한 사항

• phone_book의 길이는 1 이상 1,000,000 이하입니다.
  • 각 전화번호의 길이는 1 이상 20 이하입니다.
  • 같은 전화번호가 중복해서 들어있지 않습니다.

입출력 예제

phone_book	return
["119", "97674223", "1195524421"]	false
["123","456","789"]	true
["12","123","1235","567","88"]	false

 

나는 이문제를 HashSet을 사용해서 풀려고 했다.

 

그 이유는 일단 hash는 문자열을 비교하는데에 있어서 빠른 검색 속도를 가지고 있고 중복을 허용하지 않는다고 했기때문이다.

 

하지만 여기까지의 접근은 좋았지만 나는이전에 풀었던 문제에서 시간 복잡도때문에 애를 먹어서

시간복잡도를 줄이기 위해서 이중 for문이 아닌 방식을 생각해내려고 했다.

 

물론 이중 for문이 아니더라도 몇몇개의 테스트케이스를 통과할수 있었지만 접두사 부분때문에 애를 먹었다.

그리고 효율성에서도 많이 떨어졌다.

 

혼자 도저히 하다가 안되서 시간 낭비하는것보단 얼른 보고 소스 이해하고 넘어가는것이 나을것같아

구글 검색을 하였다.

 

하지만 다른 사람들은 모두 이중 for문을 통해서 이 문제를 풀었다.

속으로도 이중 for문이 아니고서는 도저히 못풀거같은데 라는 생각을 했지만 역시였다.

 

무튼 그렇게 해서 나온 소스는 아래와 같았다.

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        
        HashSet<String> set = new HashSet<>();
        
        //HashSet에다가 전화번호 집어 넣음
        for(String phone : phone_book){
            set.add(phone);
        }
        
        for(String phone : phone_book){
            for(int i = 0;i< phone.length();i++){
                if(set.contains(phone.substring(0,i))){
                    return false;
                }
            }
        }
        
        return answer;
    }
}

사실 이렇게 하기 이전에 나는 startsWith()라는 메소드를 가지고 배열안의 문자와 hash안의것과 비교를 했는데

그렇게 하니 효율성 테스트 에서 떨어져서 substring()메소드를 사용해보니 성공했다.

 

이번 문제를 풀면서 느낀점은 

 

1. 이중 for문을 써야 할거같을땐 무조건 쓰고 하다가 효율성 테스트에서 떨어지면 다른걸 생각해봐라

2. for문 한개 안에 여러 작업을 처리하는것보다 이중 for문안에 작업이 적은게 효율이 더 좋을때도 있다.

3. startWith()보다 substring()의 처리속도가 더 빠르다.