[Programmers]#Level2_전화번호 목록, 해시 자료구조, us 컨테이너, 트라이 검색 트리

 

#1. 문제

 

프로그래머스

 

---

 

#2. 풀이

 

1. 트라이 검색 트리

// 링크 추가

 

2. unorderd_set 컨테이너

 

[Basic C++] #29_Set, STL 컨테이너

unordered_set 컨테이너는 중복을 허용하지 않는 연관 컨테이너입니다. unordered_set 컨테이너는 해시 자료구조를 통해 구현되어 있으며, 내부적으로 정렬 작업을 수행하지 않습니다. 이 외 동작들을 은 대부분 set 컨테이너와 동일합니다.

 

3. 전화번호를 하나씩 추가해가며, us 컨테이너에 있는지 확인! 

 

1. 주어진 전화 번호 목록을 순회하며, 각 전화번호를 us 컨테이너에 삽입합니다.
2. 주어진 전화 번호전화번호 목록을 순회하며, 현재 전화번호의 각 번호를 비어있는 string 변수의 뒤에 삽입하는 동시에 us 컨테이너에 동일한 문자열이 존재하는지 확인해 줍니다.
3. 트라이 검색 트리를 활용해도 좋을 문제입니다!

 

---

 

#3. 코드

 

// unordered_set 활용 : 해시 자료구조 활용 문제, 하지만 트라이 자료구조 혹은 문자열 정렬을 통해 풀이하는게 더 효율적인 방법을 보임...

#include <string>
#include <vector>
#include <unordered_set>

using namespace std;

bool solution(vector<string> phone_book)
{
    unordered_set<string> us;

    for (int i = 0; i < (int)phone_book.size(); ++i)
        us.insert(phone_book[i]);

    for (int i = 0; i < (int)phone_book.size(); ++i)
    {
        string num = "";
        for (int j = 0; j < (int)phone_book[i].size(); ++j)
        {
            num += phone_book[i][j];
            auto it = us.find(num);
            if (it != end(us) && num != phone_book[i])
            {
                return false;
            }
        }
    }

    return true;
}

 

---