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

문제 설명

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

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

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

• 구조대 : 119
• 박준영 : 97 674 223
• 지영석 : 11 9552 4421

전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

 

제한 사항

• phone_book의 길이는 1 이상 1,000,000 이하입니다.
• 각 전화번호의 길이는 1 이상 20 이하입니다.

 

입출력 예제

phone_book                                                                                                 return

[119, 97674223, 1195524421]	false
[123,456,789]	true
[12,123,1235,567,88]	false

 

입출력 예 설명

입출력 예 #1
앞에서 설명한 예와 같습니다.

입출력 예 #2
한 번호가 다른 번호의 접두사인 경우가 없으므로, 답은 true입니다.

입출력 예 #3
첫 번째 전화번호, “12”가 두 번째 전화번호 “123”의 접두사입니다. 따라서 답은 false입니다.

 

---

풀이

- 선 정렬 (문자열 정렬이기 때문에 사전정렬이 됨)

- 바로 다음 번호가 현재 번호로 시작하는지 확인 -> startsWith : 특정 문자열로 시작하는지 체크가능한 함수

import java.util.Arrays;

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

 

셀프 피드백

- 해시를 어디다 써야할지 모르겠음

- 처음엔 숫자 오름차순 정렬이라고 생각해서 이중 for문을 썼었음

 

 

기타 코드들

1. 정규표현식 사용

import re
def solution(phoneBook):

    for b in phoneBook:
        p = re.compile("^"+b)
        for b2 in phoneBook:
            if b != b2 and p.match(b2):
                return False
    return True

 

2.Trie 알고리즘 사용

- 해당 알고리즘 관련 포스팅 : https://bb-dochi.tistory.com/40

import java.util.HashMap;
import java.util.Map;

class TrieNode{
    HashMap<Character, TrieNode> childNodes = new HashMap<>();
    boolean isLastChar;
    
    HashMap<Character,TrieNode> getChild(){
        return this.childNodes;
    }
    
    boolean getIsLastChar(){
        return isLastChar;
    }
    
    void setIsLastChar(boolean isLast){
        this.isLastChar = isLast;
    }
}

class Trie {
    TrieNode root;
    
    Trie(){
        root = new TrieNode();
    }
    
    void insert(String str){
        TrieNode current = this.root;
        
        for(char c : str.toCharArray()){           
            //자식노드로 계속 넘어가면서 없으면 생성
            current = current.getChild().computeIfAbsent(c, f-> new TrieNode());
        }
        
        //마지막 글자에는 마지막 표시
        current.setIsLastChar(true);
    }
    
    //해당 문자열로 시작하는 문자열이 있는지 탐색
    boolean find(String str){
        TrieNode current = this.root;
        
        for(char c : str.toCharArray()){
        	//전부 탐색하기 전에 끝났다고 체크되면 접두사가 있다는 의미
            if(current.getIsLastChar()){
                return false;
            }
            
            current = current.getChild().get(c);  
        }  
        
        return true;
    }
}


class Solution {  
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        Trie trie = new Trie();
        
        for(String number : phone_book){
            trie.insert(number);
        }
        
        for(String number : phone_book){
            answer = trie.find(number);
            
            if(!answer)
                break;
        }
        
        return answer;
    }
}

- 트라이 알고리즘을 사용해, 하나씩 insert 해주고

- 나중에 find 함수로 탐색하면서 끝까지 탐색하기 전에 isLastChar가 true면 접두사가 있다는 것으로 판정

- 미리 정렬을 한다면 find 함수를 쓰지 않고 insert에서 넣으면서 바로 체크 가능 

 

 

2-1. Trie알고리즘 - 정렬ver

import java.util.HashMap;
import java.util.Map;
import java.util.Arrays;

class TrieNode{
    HashMap<Character, TrieNode> childNodes = new HashMap<>();
    boolean isLastChar;
    
    HashMap<Character,TrieNode> getChild(){
        return this.childNodes;
    }
    
    boolean getIsLastChar(){
        return isLastChar;
    }
    
    void setIsLastChar(boolean isLast){
        this.isLastChar = isLast;
    }
}

class Trie {
    TrieNode root;
    
    Trie(){
        root = new TrieNode();
    }
    
    boolean insert(String str){
        TrieNode current = this.root;
        
        for(char c : str.toCharArray()){      
            //전부 삽입 전에 isLastChar이 true라면 접두사 있다는 것
            if(current.getIsLastChar()){
                return false;
            }
            
            //자식노드로 계속 넘어가면서 없으면 생성
            current = current.getChild().computeIfAbsent(c, f-> new TrieNode());
        }
        
        //마지막 글자에는 마지막 표시
        current.setIsLastChar(true);
        return true;
    }
}

class Solution {  
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        Trie trie = new Trie();
        
        Arrays.sort(phone_book);
        
        for(String number : phone_book){
            answer = trie.insert(number);
            if(!answer) break;
        }
        
        return answer;
    }
}