[프로그래머스] 전화번호 목록

https://programmers.co.kr/learn/courses/30/lessons/42577

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

2021-08-05

---

1. Trie

import java.util.*;
class Solution {
    static class TrieNode {
        TrieNode[] next;
        boolean isLast;
        TrieNode() {
            next = new TrieNode[10];
            this.isLast = false;
        }
    }
    static class Trie {
        TrieNode root;
        Trie() {
            root = new TrieNode();
        }
        void insert(String word) {
            TrieNode node = root;
            for(int i = 0; i < word.length(); i++) {
                int w = Character.getNumericValue(word.charAt(i));
                if(node.next[w] == null) node.next[w] = new TrieNode();
                node = node.next[w];
            }
            node.isLast = true;
        }
        boolean contains(String word) {
            TrieNode node = root;
            for(int i = 0; i < word.length(); i++) {
                int w = Character.getNumericValue(word.charAt(i));
                if(node.next[w] == null) return false;
                node = node.next[w];
                if(node.isLast) return true;
            }
            if(node.isLast) return true;
            return false;
        }
    }
    static boolean solution(String[] phone_book) {
        boolean answer = true;
        Arrays.sort(phone_book);
        
        Trie t = new Trie();
        for(int i = 0; i < phone_book.length; i++) {
            if(!t.contains(phone_book[i])) t.insert(phone_book[i]);
            else {
                answer = false;
                break;
            }
        }
        return answer;
    }
}

#문제풀이

Trie 자료구조 복습 겸 풀어봤다. 

 

---

 

2. startsWith

import java.util.*;
class Solution {
    static 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;
    }
}

 

#문제풀이

사실 Trie까지 안 써도 된다. Arrays.sort로 비교 해놓고 앞에서부터 하나씩 startsWith로 바로 다음 값을 체크해주면 된다.