[LV.2][JAVA] 전화번호 목록

https://school.programmers.co.kr/learn/challenges?tab=algorithm_practice_kit

프로그래머스

푸는 동안 사고과정 및 개선점

처음에 진짜 감이 안잡혔다. 접두어 처리를 해서 contains를 하면 될 것 같은데, 이게 Hash가 맞나?? 이런 생각이 머리 속에 맴돌았다.

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        TreeSet<String> ts = new TreeSet();
        for(String phone: phone_book){
            ts.add(phone);
        }
        
        // 각 전화번호의 모든 접두어를 확인
        for (String phone : phone_book) {
            for (int i = 1; i < phone.length(); i++) { // 길이는 1이상
                String prefix = phone.substring(0, i);
                if (ts.contains(prefix)) {
                    answer = false;
                }
            }
        }
        
        return answer;
    }
}

2중 포문은 어쩔 수 없는 것 같다. 그래도 contains로 해서 조회 때 O(1)을 해줘서 좀 빠른 게 아닐까

중복된 번호가 없으니까 HashSet에 넣어서 조회 성능을 올려주고, 각 번호를 돌면서 substring을 잘라 이게 HashSet에 존재하는 것인지 찾는다. 이러면 존재할 경우 접두어가 있는 Set이 된다.

---

# 추가 공부

substring은 ` [ startIndex, endIndex ) ` 다. 이상, 미만이기 때문에 주의해야된다.

 

도움이 됐다면 댓글이나 공감 버튼 한 번씩 누르고 가주세요!