프로그래머스 문제 풀이 전화번호 목록

Gurumee 2019. 11. 5. 15:34

문제 URL 전화번호 목록

문제 지문 파악하기
구르미의 알고리즘 풀이

문제 지문 파악하기

이 문제는 전화번호부에 존재하는 번호 중, 다른 전화번호가 접두어인지 판별하는 문제, 즉 다른 전화번호로 시작하는 전화번호가 있는지, 판별하는 문제입니다. 정말 쉽게 풀면 전화번호부를 2번 순회하여, 해당 번호와 다른 번호를 비교하는 방법이 있습니다. 첫 번째 입력을 통해서 찬찬히 살펴보겠습니다.

입력: ["119", "97674223", "1195524421"]

여기서 "119"를 기준으로 "97674223", "1195524421" 순서대로 시작하는 문자열이 있는지 판별합니다.

"119" - "97674223" : 둘 다 서로에게 시작하는 번호로 쓰이지 않음.
"119" - "1195524421" : "1195524421"는 "119"로 시작함

그렇기 때문에 False를 반환하게 됩니다. 이번엔 다른 입력을 살펴보도록 하죠.

입력: ["123", "456", "789"]

여기서 "123"를 기준으로 "456", "789" 순서대로 시작하는 문자열이 있는지 판별합니다.

"123" - "456" : 둘 다 서로에게 시작하는 번호로 쓰이지 않음.
"123" - "789" : 둘 다 서로에게 시작하는 번호로 쓰이지 않음.

이제 "456" 기준으로 "789"와 비교합니다.

"456" - "789" : 둘 다 서로에게 시작하는 번호로 쓰이지 않음.

모든 문자열을 순회했음에도 서로에게 시작하는 번호로 쓰이는 번호를 찾을 수 없습니다. 그래서 이 입력은 결과가 True를 반환하게 됩니다. 알고리즘이 어떠헤 동작하는지 아시겠지요? 이 알고리즘을 토대로 코드를 기술하면 다음과 같습니다.

def solution(phone_book):
    size = len(phone_book)
    
    for i in range(size-1):
        phone = phone_book[i]
        
        for j in range(i+1, size):
            other = phone_book[j]
            
            if phone.startswith(other) or other.startswith(phone):
                return False
        
    return True

이렇게 하면, 시간 복잡도는 O(N ^ 2)이 됩니다.

구르미의 알고리즘 풀이

위의 코드로 제출해도 사실 통과합니다. 굳이 "해시"를 사용해서 효율성을 올릴 필요가 없어요. 그래서 풀이보다는 그냥 코드만 기술하도록 하겠습니다.

def solution(phone_book):
    d = dict()

    for phone in phone_book:
        for key in d.keys():
            if key.startswith(phone) or phone.startswith(key):
                return False

        d[phone] = phone

    return True

# main 함수
if __name__ == '__main__':
    phone_book = ["119", "97674223", "1195524421"]
    result = solution(phone_book)
    print(result)

위의 코드를 제출하면, 효율성 체크 시 0.01~0.02ms 정도 빠르게 통돠하는 것을 확인할 수 있습니다. 허나, "해시를 이렇게 사용해서 알고리즘을 풀라는 것이 의도일까?"라는 의문점이 남습니다. cpp 코드는 다음과 같습니다.

#include <string>
#include <vector>
#include <map>

#include <iostream>

using namespace std;

bool solution(vector<string> phone_book) {
    map<string, string> d;
    
    for (const auto& phone : phone_book) {
        
        for (const auto set : d) {
            string key = set.first;
            
            if (key.rfind(phone, 0) == 0 || phone.rfind(key, 0) == 0 ) {
                return false;
            }
        }
        
        d[phone] = phone;
    }
    
    return true;
}

int main() {
    vector<string> phone_book = { "119", "97674223", "1195524421" };
    auto result = solution(phone_book);
    cout << result << endl;
    return 0;
}

728x90

저작자표시

티스토리