Programmers 42577 - 전화번호 목록

코딩테스트 연습 - 전화번호 목록 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 한다.

예를 들어 ["119", "97674223", "1195524421"] 이 주어졌다면 “119”는 “1195524421”의 접두어가 됩니다.

어떤 번호가 다른 번호의 접두어인 경우가 있으면 false 그렇지 않다면 true

우선 접두어라는 것이 앞에 있다는 소리니 길이가 짧을 수밖에 없다. 주어진 배열을 길이로 정렬부터 하는 게 맞다는 생각이 든다.

트라이를 사용할까?

트라이를 구성하고 길이가 짧은 단어 부터 삽입해 간다.

삽입도중에 단어가 완성됐다는 플래그가 나오면 false를 반환하고 종료한다.

import java.util.*;

class Solution {
    static class TrieNode {
        Map<Character, TrieNode> children = new HashMap<>();
        boolean isEndOf = false;
        
        public boolean isEndOf() {
            return isEndOf;
        }
        
        public void setEndOf(boolean end) {
            isEndOf = end;
        }
    }
    
    static class Trie {
        TrieNode root;
        
        public Trie() {
            root = new TrieNode();
        }
        
        public boolean insert(String word) {
            TrieNode current = root;
            for (char ch : word.toCharArray()) {
                current.children.putIfAbsent(ch, new TrieNode());
                current = current.children.get(ch);
                if (current.isEndOf()) {
                    // 삽입중인데 이미 단어가 완성된게 있다 -> 접두어 존재
                    return false;
                }
            }
            current.setEndOf(true);
            return true;
        }
    }
    
    public boolean solution(String[] phone_book) {
        Arrays.sort(phone_book, (a, b) -> Integer.compare(a.length(), b.length()));
        Trie trie = new Trie();
        for (String number : phone_book) {
            if (!trie.insert(number)) {
                return false;
            }
        }
        
        return true;
    }
}

 

그런데 이 문제는 잘 생각해 보면 그럴 필요가 없다. 그냥 정렬해서 이전 것과 비교하면 된다. 문자열의 정렬은 사전순으로 이루어진다. 예를 들어 ["119", "97674223", "1195524421"] 이것의 정렬의 결과는 ["119", "1195524421", "97674223"] 이 된다. 따라서 접두어는 반드시 한 칸 앞에 존재한다.

import java.util.*;

class 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;
    }
}