프로그래머스 완주하지 못한 선수 C++

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

해시 문제입니다. 배열로 들어오는 번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하는 문제입니다.

C++을 공부하기 위해 기록하는 중입니다.

 

예를 들어, ["119", "97674223", "1195524421"]같은 경우 119가 '119'5524421의 접두사가 되므로 false를 반환합니다.

 

Map? Unorded Map?

일반적으로 알고있는 map과 unorded_map은 무슨 차이가 있는지에 대해 알아봤습니다.

map의 경우 내부적으로 이진 검색 트리를 사용하는 구조입니다. 따라서 값을 넣게 된다면 자동으로 정렬됩니다. 키에 대한 검색, 삽입, 삭제 작업의 시간 복잡도는 O(log n)입니다.
키의 순서가 중요하거나 정렬된 데이터를 필요로 할 때 유용합니다.

 

unorded_map의 경우에는 내부적으로 해시테이블을 사용합니다. 해시테이블은 해시 함수를 사용해 입력 키를 데이터가 저장된 위치로 직접 변환합니다. 이 과정을 통해, 데이터의 위치를 바로 계산하므로, 데이터를 검색, 삽입, 삭제할 때 해당 위치로 바로 접근할 수 있습니다. map에 비해 평균적으로 빠르다는 의미입니다.

 

즉, 키의 자동 정렬이 필요하거나 순서대로 데이터에 접근해야 할 경우 map을 사용하고, 그렇지 않고 성능 최적화가 중요한 경우 unordered_map을 사용하는 것이 좋습니다.

 

이 문제의 경우 정렬이 필요하지 않으므로 unordered_map을 사용했습니다.

 

외부 반복문(i 인덱스)은 phone_book의 각 전화번호를 순회합니다.
내부 반복문(j 인덱스)은 현재 검사 중인 전화번호의 각 문자를 하나씩 추가하면서 부분 문자열을 생성합니다.
생성된 부분 문자열이 해시맵에 존재하고, 동시에 현재 전체 전화번호와 동일하지 않은 경우, 이는 다른 번호의 접두어임을 의미합니다.

이 때 이미 답이 결정되었기 때문에 바로 false를 반환했습니다.

for(int i = 0; i < phone_book.size(); i++) {
    string phone_number = "";
    for(int j = 0; j < phone_book[i].size(); j++) {
        phone_number += phone_book[i][j];
        if(hash_map[phone_number] && phone_number != phone_book[i])
            return false;
    }
}

 

 

전체 코드입니다.

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

using namespace std;

bool solution(vector<string> phone_book) {
    bool answer = true;

    unordered_map<string, int> hash_map;
    for(int i = 0; i < phone_book.size(); i++)
        hash_map[phone_book[i]] = 1;

    for(int i = 0; i < phone_book.size(); i++) {
        string phone_number = "";
        for(int j = 0; j < phone_book[i].size(); j++) {
            phone_number += phone_book[i][j];
            if(hash_map[phone_number] && phone_number != phone_book[i])
                answer = false;
        }
    }

    return answer;
}