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

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/42577

 

메모

- 모든 전화번호 각각에 대해서 string 배열값 앞에서부터 비교? 더 작은 거 길이만큼 for문 돌려서 긴 거랑 비교해서 풀려고 했는데... 이렇게 되면 더 작은 모든 문자열에 대해서 for문을 돌려야 됨. 모든 문자열 개수-1 * 작은 문자열의 길이 만큼 for문 돌리면 시간 초과가 뜨겠지...

- 해시 맵에 가능한 문자열들을 value 값이 1인 key로 넣어서 그 해시맵을 대상으로 문자열들을 돌리는 코드를 작성해야 됨

 

 

맞힌 코드

#include <bits/stdc++.h>

using namespace std;

bool solution(vector<string> phone_book) {
    bool answer = true;
    
    // HashMap
    unordered_map<string, int> map;
    for (int i=0; i<phone_book.size(); i++){
        map[phone_book[i]] = 1;  // 전화번호 목록에 1개 존재함을 표시
    }
    
    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]){
                answer = false;
            }
        }
    }

    return answer;
}

 

 

참고)

https://coding-grandpa.tistory.com/90

[프로그래머스] 전화번호 목록 문제 풀이(해시 Lv. 2) - C++

 

HashMap

https://dev-nicitis.tistory.com/52

UNSEEN 대비 4. C++ 주요 컨테이너 (2) (map, unordered_map)

https://marmelo12.tistory.com/316

[C++ STL] std::unordered_map(연관 컨테이너)