전화번호 목록 - 프로그래머스, c++

 

 

- 문제 풀이

"해시"를 이용하는 문제이다.

앞선 해시 문제들과 같이 해시를 사용하기 위한 #include <unordered_map> 을 불러온 후,

해시테이블에 값 저장, 해시테이블을 순회하며 주어진 문제를 해결한다.

 

 

- 코드

처음에 내가 작성한 코드는 다음과 같다.

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

bool solution(vector<string> phone_book) {
    bool answer = true;
    unordered_map<string, int> temp;
    
    //해시테이블에 값 저장
    for (string phone : phone_book) {
        temp[phone]++;
    }
    
    //해시테이블 순회
    for (auto pair : temp) {
        for(auto pair2 : temp) {
            if(pair.first != pair2.first) {
                if( pair.first == (pair2.first).substr(0,(pair.first).size()) ) {
                    answer = false;
                    break;
                }
            }
        }
        if (!answer) {
            break;
        }
    }
    
    return answer;
}

 

 

정확도 테스트는 통과 했으나 효율성 테스트에서 통과하지 못했다.

 

 

효율성 문제를 해결하기 위해 해시테이블 순회 단계 코드에서 더 간단한 방법을 찾아야만 했다.

아래 처럼 pair이 아닌 phone_book[i] 이렇게 string을 불러오는 형태로 접근하며 문제를 해결할 수 있었다.

 

이 문제 역시 #include <algorithm>을 이용해 알고리즘 복잡도를 줄이는 방법이 있는 것 같다.

나중에 그에 대한 공부도 해봐야겠다.

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

using namespace std;

bool solution(vector<string> phone_book) {
    unordered_map<string, int> map;
    for (int i = 0; i < phone_book.size(); i++)
        map[phone_book[i]] = 1;

    // 모든 전화번호의 substring이 HashMap에 존재하는지 확인하기
    for (int i = 0; i < phone_book.size(); i++)
    {
        for (int j = 0; j < phone_book[i].size() - 1; j++)
        {
            string phone_number = phone_book[i].substr(0, j + 1);
            if (map[phone_number])
                return false;
        }
    }
    
    return true;
}

(코드 출처: https://coding-grandpa.tistory.com/90)