[프로그래머스] 전화번호 목록 (C++)

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

코딩테스트 연습 - 전화번호 목록

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

struct {
    bool operator()(string &first, string &second){
        return first.size() < second.size();
    }
} cmp;

bool solution(vector<string> phone_book) {
    bool answer = true;
    map<string, int> m;
    sort(phone_book.begin(), phone_book.end(), cmp);
    for (string num: phone_book){
        string s="";
        for (int i=0; i<num.size(); i++){
            s+=num[i];
            if (m.find(s)!=m.end())
                return false;
        }
        m[s]=1;
    }
    return answer;
}

map을 이용하는 문제.

 

내가 푼 방식은 이렇다.

- 길이 순으로 번호들을 정렬한다.

- 정렬한 list를 순회해 가면서, 한 번호를 (1자리, 2자리,... n자리) 씩 읽어들이고 만약 동일한 문자열이 map 내에 존재한다면(find 함수 이용) false를 리턴하고, 아닐 경우에는 쭉 돌다가 map에 그 문자열을 추가해준다. 

 

다른 분들의 풀이를 보니, unordered map을 이용한다. unordered_map은 해쉬테이블로 구현한 자료구조로 탐색 시간복잡도는 O(1)이다. unordered map에 번호들을 모두 다 넣어준뒤(map[문자열]=1 이런 형태로) , phone_book 리스트를 순회하면서 한 번호를 (1자리, 2자리,... n자리) 씩 읽어들이고, 동일한 문자열이 hashmap 내에 존재한다면 false를 리턴한다.