[알고리즘] 전화번호 목록

• 포인트
• 짧은 아이디어가 중요한 것 같다. string 은 기본 정렬은 string 의 크기순
• find 함수를 써서 뒤에 string 에 포함이 되어 있는지를 확인 안되어 있으면 string::npos 하고 비교를 한다.

---

 

• 문서가 수정되었습니다.    (2021.03.18)
• 문자열은 정렬을 하게 되는 경우 길이와 상관없이 앞글자를 기준으로 정렬되면 그 이후 길이로 정렬이 됩니다. 
• 처음에는 포함되지 못한 경우를 고려하였으나 반례가 생겼고 맨 앞 인덱스에서 발견하지 못하는 경우로 바꾸었습니다. 

🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. 

c++/cpp

#include <bits/stdc++.h>

using namespace std;

bool solution(vector<string> phoneBook) {
    sort(phoneBook.begin(), phoneBook.end()); //string 정렬 크기순

    for ( int i = 0 ; i < phoneBook.size() - 1 ; i++ )
    {
        auto a =phoneBook[i+1].find(phoneBook[i]);
        if(a==0) 
            return false;
    }

    return true;
}

python

def solution(phone_book: list) -> bool:
    phone_book = sorted(phone_book)
    for index in range(len(phone_book) - 1):
        if phone_book[index + 1].startswith(phone_book[index]):
            return False
    return True


def solution(phone_book: list) -> bool:
    phone_book = sorted(phone_book)
    for index in range(len(phone_book) - 1):
        if phone_book[index + 1].startswith(phone_book[index]):
            return False
    return True

with hash

 

from collections import defaultdict

def solution(phone_book: list):
    answer = True
    hash = defaultdict()
    for phone_number in phone_book:
        hash[phone_number] = 1
    for phone_number in phone_book:
        temp = ""
        for number in phone_number:
            temp += number
            if temp in hash and temp != phone_number:
                answer = False
    return answer