p42577.md

42577. 전화번호 목록

Summary

🙇‍♂️ URL : https://programmers.co.kr/learn/courses/30/lessons/42577
🤷‍♂️ Difficulty: ?
💆‍♂️ Submissions : Success

Source code

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

How to Approach

해시로 풀어야 한다고 적혀있어서 열심히 key,value 쌍을 만들었는데, 테스트케이스는 다 통과했지만 효율성에서 결국 능선을 넘지 못했다.

근데 가만..히 생각해보니 굳이 이렇게 어렵게 해시도 써야하나? 싶기도 하고. 어차피 문자열을 아스키 기반으로 정렬되니까 비슷한 문자열끼리 정렬해주고 앞뒤로 비교해주면서 접두어(startWith)가 맞으면 false, 일치되는게 결국 하나도 없으면 true를 반환해주도록 구현하였다.

결과는 아주 가볍게(?) 성공.

추가로 해시맵을 사용해보았다. 비록 효율성의 능선을 넘지는 못했지만, 그래도 테스트케이스는 모두 통과(?)했으니 같이 공유해둔다. key는 자동으로 incrementional하게 만들어주고, value를 비교해주면서 startWith인 경우 반환해주는 방식으로 진행했다.

class P42577_Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;

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

        for(int i=0; i<phone_book.length; i++) {
            Iterator<Map.Entry<Integer, String>> entries = map.entrySet().iterator();
            while(entries.hasNext()){
                Map.Entry<Integer, String> entry = entries.next();
                if(!phone_book[i].equals(entry.getValue()) && entry.getValue().startsWith(phone_book[i])) {
                    return false;
                }
            }
        }
        return true;
    }
}