[PG] 전화번호목록 - Java

[원문 링크]

https://adorable-aspen-d23.notion.site/PG-c556306cdc3440e58031178200b40e55

[PG] 전화번호목록

코딩테스트 연습 - 전화번호 목록

코딩테스트 연습 - 전화번호 목록

[풀이]

• hash라고 되어 있지만 문제 보자마자 트라이 사용하는 것 같아서 트라이 사용해봤다.
• 근데 런타임에러 자꾸 나ㅡㅡ 메모리 초과인가 싶어서 처음에 TrieNode에서 child 배열로 사용하던거 Map으로 바꿔줬는데도 케이스 14-20 싹다 런타임이고 효율성도 런타임에러 ㅠㅠ
• 그래서 문제가 뭔지 살펴봤는데 로직상으로는 맞아서 아무리봐도 안보였는데 알고보니 처음에 배열 정렬할 때 Comparator 사용한게 문제였던것..
• {”123”,”12”,”21”} 을 정렬시킬 때 처음에는 트라이 쓰니까 길이가 짧은 것 부터, 그리고 같은 길이에서는 오름차순으로 정렬하기 위해 <수정전>처럼 Comparator를 사용했는데 ⇒ [12, 21, 123]으로
• 어차피 지금 접두사만 비교하니까 길이가 짧은 것 부터 할 필요 없고 그냥 기본 string정렬로 해도 되는 것이었다. ⇒ [12, 123, 21] 로 정렬됨
• 사실 수정전처럼 해도 답은 맞는다. 근데 Comparator쓰면 속도가 엄청 느려지는 듯..?
• Trie개념은 여기를 참고하자
•  

<수정전>

Arrays.sort(phone_book, new Comparator<String>() { //길이로 정렬
      @Override
      public int compare(String o1, String o2) {
          if(o1.length() > o2.length()){
              return 1;
          }
          else if(o1.length() < o2.length()){
              return -1;
          }
          else{
              return Integer.compare(Integer.parseInt(o1),Integer.parseInt(o2));
          }
      }
  });

<수정후>

Arrays.sort(phone_book);

[풀이]

import java.io.*;
import java.util.*;

class Solution {
    static boolean answer;
    static MyTrie trie = new MyTrie();

    public boolean solution(String[] phone_book) {
       answer = true;
        Arrays.sort(phone_book);

        for(String str:phone_book){
            trie.insert(str);
        }
        return answer;
    }

    static class MyTrie{
        TrieNode root = new TrieNode();

        public void insert(String input){
            TrieNode now = root;

            for(int i=0;i<input.length();i++){
                char ch = input.charAt(i);
                if(now.isEnd){ //지금 노드가 마지막이라는 것은 이미 거쳤다는 뜻
                    answer = false;
                    return;
                }
                if(now.hasChild(ch)){ //자식이 있으면 그냥
                    now = now.getChild(ch);
                }
                else{
                    now.child.put(ch,new TrieNode()); //자식이 없으면 자식 새로 추가
                    now = now.getChild(ch);
                }
            }
            now.isEnd = true;
        }
    }

    static class TrieNode{
        Map<Character, TrieNode> child = new HashMap<>();
        boolean isEnd = false;

        boolean hasChild(char node){
            if(child.containsKey(node)){
                return true;
            }
            else{
                return false;
            }
        }

        TrieNode getChild(char node){
            return child.get(node);
        }
    }
}

얻어가는 것

• 소팅할 때 Comparator를 사용하면 시간이 엄청 많이 늘어나네..? 뭐지 만약 무조건 사용해야 하면 어떻게 사용하라는거지 흠

느낀점

"220328"

소요 시간 : 1h