[C++] Programmers Lv. 2 "전화번호 목록"

🔵 문제 링크

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

프로그래머스

 

🔵 알고리즘

• 전화번호를 key 값으로 하여 unordered_map에 등록한다.
• 전화번호를 각각 순회하며 현재 번호가 다른 번호로 시작하는지 확인한다. 전화번호의 길이가 최대 20이므로 부담없이 순회할 수 있다.

// 현재 번호가 접두사로 이루어진 번호인지 확인
bool isPrefix(string number)
{
    string prefix = "";
    for (char c : number)
    {
        prefix += c;
        
        if (phone.find(prefix) != phone.end() && prefix != number)
            return true;
    }

    return false;
}

 

위 코드는 현재 번호가 다른 번호로 시작하는지 확인하는 함수이다.

현재 번호(문자열)를 하나씩 증가하여 비교하면서 그 번호가 이미 hash에 등록되어 있는지 확인한다.

 

이때, unordered_map.find() 함수를 사용하였다. 

unordered_map[임의값]을 할 경우, map에 해당 값이 없으면 자동으로 그 값을 새로 생성한다.

이는 불필요한 행위이므로, find()를 사용해서 현재 번호가 hash에 등록되어있는지만 확인했다.

 

참고로, unordered_map.find()는 원하는 값을 찾지 못하였다면 end() 값을 반환한다.

 

🔵 전체 코드

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

using namespace std;

// 1. 정렬으로 하는 방법
// 2. 해시

unordered_map<string, bool> phone;

// 현재 번호가 접두사로 이루어진 번호인지 확인
bool isPrefix(string number)
{
    string prefix = "";
    for (char c : number)
    {
        prefix += c;
        
        if (phone.find(prefix) != phone.end() && prefix != number)
            return true;
    }

    return false;
}

bool solution(vector<string> phone_book) {
    // hash에 등록
    for (string str : phone_book)
        phone[str] = true;

    for (string str : phone_book)
    {
        if (isPrefix(str))
            return false;
    }

    return true;
}

 

🔵 시간 복잡도

번호의 최대 길이를 M, phone_book의 최대 길이를 N이라 했을 때 solution 함수의 마지막 for문에서 시간 복잡도는 O(N * M^2)이다.

N * M^2이라 안 좋은 것 같아 보일 수 있는데, M이 최대 20으로 매우 작은 편이므로 통과할 수 있었다.

 

🔵 참고

다른 풀이 방법으로는 phone_book을 정렬하여 비교하는 방법이 있다.