[해시] Level 2 전화번호 목록

문제 설명

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

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

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

 

 

제한 사항

• phone_book의 길이는 1 이상 1,000,000 이하입니다.
  • 각 전화번호의 길이는 1 이상 20 이하입니다.
  • 같은 전화번호가 중복해서 들어있지 않습니다.

 

입출력 예시 및 설명

---

풀이)

2가지 알고리즘을 사용하여 구현하였다

 

1. 정렬 및 반복문을 사용하는 방법

어차피 접두사가 같은 번호들은 배열을 정렬하면 나란히 서게 된다

예를 들어 {123, 456, 12345} 배열이라면 정렬하면 {123, 12345, 456} 이런 식으로 된다

즉, 접두사와 그를 포함한 번호는 나란히 위치하게 되고, 접두사가 더 짧으므로 항상 앞에 오게 되는것이다

그래서 phone_book 배열을 먼저 정렬하고 반복문을 통해 앞과 뒤를 비교하여 구하는 방식이 있다

 

2. 해시 사용

그래도 명색이 해시 문제인데 해시로도 풀어봐야하니까 고민했다

몇 번 고민하다가 너무 오래걸려서 그냥 다른 사람의 풀이를 참고했다

이렇게 하다보면 실력이 늘겠지!!

아무튼 알고리즘을 설명하자면 이러하다

 

phone_book 리스트를 hasp map을 생성하여 저장한다

그리고 반복문을 통해 접두어를 얻어와서 해당 접두어가 hash map에 존재하는지 판단한다

예를 들어 123이면 다른 번호들 중에 1이 있는지 검사하고, 다음으로 12가 있는지 검사하고 마지막으로 123이 있는지 검사하는 것이다

이 때 당연히 아예 같은건 무시해야 한다

자세한건 코드로 보자

 

 

[ 파이썬 구현 ]

코드를 그냥 반복문으로 구현한 것과 Hash map을 사용하여 구현한 것 모두 정리해볼 것이다

 

먼저 아래의 코드는 틀린 코드이다

#틀린 코드
def solution(phone_book):
    answer = True
    phone_book.sort()
    
    for i in range(len(phone_book)-1):
        if phone_book[i] in phone_book[i+1]:
            answer = False
            break
            
    return answer

우리는 접두사 비교이기 떄문에 맨 앞의 번호가 일치하는지를 확인해야 한다

하지만 이렇게 구현하면 문장 위치 상관없이 포함 여부만 알려주기 떄문에 안된다!

그래서 이렇게 하면 테스트케이스 중 한 개를 틀리게 된다ㅠ

 

 

이제 아래는 수정한 코드이다

#정렬 및 반복문 사용
def solution(phone_book):
    answer = True
    phone_book.sort()
    
    for i in range(len(phone_book)-1):
        if phone_book[i] in phone_book[i+1][:len(phone_book[i])]:
            answer = False
            break
            
    return answer

앞의 틀린 코드에서 비교하는 문장을 접두사의 길이만큼 앞에서부터 잘라서 비교하는 걸로만 바꿨다

아직까지는 다른 사람 코드를 약간 참고해야한다...

역시 파이썬은 정은 안가는데 막상 구현해놓으면 쉬워서 안할 수가 없다;;

 

 

마지막으로 해시 단원이니까 해시를 사용한 코드를 살펴보자

#해시 사용
def solution(phone_book):
    answer = True
    hash_map = {}
    for phone_number in phone_book:
        hash_map[phone_number] = 1
    for phone_number in phone_book:
        temp = ""
        for number in phone_number:
            temp += number
            if temp in hash_map and temp != phone_number:
                answer = False
    return answer

이건 다른 사람의 코드이다

우선 hash_map으로 딕셔너리를 생성하고

반복문을 통해 hash_map에 phone_book 리스트를 추가한다

그리고 반복문으로 하나씩 phone_book에서 번호를 꺼내고 이를 앞에서부터 한개씩 쪼개가면서 검사를 한다

만약 hash_map에 현재 temp 접두어가 존재하고, 그 접두어가 원래 번호가 아닐때

즉, 다른 번호에 temp 접두어를 갖고 있으면 False를 반환하는 것이다

이렇게 하면 이 전 코드에 비해 sort()과정이 빠지면서 효율성이 좀 더 좋아지게 된다!

 

 

 

[ C++ 코드 ]

뭔가 C++은 포기가 안돼,,,

그래서 그냥 벡터 정렬 후 비교 연산하는 알고리즘만 구현함!

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

//정렬 및 반복문 사용
bool solution(vector<string> phone_book) {
    bool answer = true;
    sort(phone_book.begin(),phone_book.end());
    for(int i=0;i<phone_book.size()-1;i++)
    {
        string str = phone_book[i+1];
        string now = phone_book[i];
        if(now==str.substr(0,now.size()))
        {
            answer=false;
            break;
        }
    }
    return answer;
}

처음에 strncmp로 했는데 왜인지 모르겠지만 안된다고 해서 실패..

그리고 compare로 했으나 그건 특정 길이만큼만 비교하는 걸 몰라서 실패.

그래서 그냥 substr로 접두사 길이만큼 자르고 둘이 비교하는걸로 했다

파이썬으로 풀다가 C++로 풀면 뭔가 복잡해진 기분인데 그래도 포기는 못해,,,

아직까진 코테에서 습관적으로 C++로 푸니까 둘이 그냥 계속 같이 공부해야지!