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

문제링크

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

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

Python

 

def solution(phone_book):
    answer = True
    dic={}
    for number in phone_book:
        dic[number]=1
    for number in phone_book:
        temp=""
        for digit in number:
            temp+=digit
            if temp in phone_book and temp!= number:
                answer=False
    return answer

아이디어: 해시 문제 정석 풀이, 사전 놓고 하나씩 꺼내서 한글자씩 돌려보며 체크.

접두어를 체크하는 것이지만 긴 것으로 작은 글자를 찾는다.

글자수가 20자 이하여서 O(N)

 

C++

#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

bool solution(vector<string> phone_book) {
    bool answer = true;
    unordered_map<string, int>hash_map;
    for (int i =0 ; i<phone_book.size();i++)
        hash_map[phone_book[i]]=1;
        
    for (int i = 0; i< phone_book.size();i++){
        string phone_number="";
        for(int j=0; j<phone_book[i].size();j++){
            phone_number+=phone_book[i][j];
        if(hash_map[phone_number] && phone_number!=phone_book[i])
            answer=false;
        
        }
   } 
    
    return answer;
}

 

아이디어: Python 과 완전히 동일