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

1. 문제 설명

2. 트러블슈팅

c++에서 해쉬맵을 사용안한지 오래 되어, 관련해서 다음 게시물을 참고하였다.

https://hanyeop.tistory.com/80

[C++] Map과 Hash Map(unordered_map) 차이 (STL)

https://life-with-coding.tistory.com/305

[C++][STL] map 사용법 정리

처음 나는 가장 짧은 단어가 무조건 접두어가 될 것이라는 (잘못된) 가정을 하고 풀어서, 

 

1. 가장 짧은 단어 구하기 

2. 해당 단어 길이만큼 잘라서 map에 넣음

3. 전화번호부 벡터 길이와 비교해서 다르면 false return

이러한 프로세스로 풀었다. 그렇게 푼 첫번째 풀이는 아래와 같다.

#include <string>
#include <vector>
#include <map>

using namespace std;

bool solution(vector<string> phone_book) {
    bool answer = true;
    int min_len = 300;
    for (int i = 0; i < phone_book.size(); i++)
        if (min_len > phone_book[i].length())
            min_len = phone_book[i].length();
    map<string, string> m;
    for (int i = 0; i < phone_book.size(); i++)
        m.insert({phone_book[i].substr(0, min_len), phone_book[i]});
    if (phone_book.size() != m.size())
        answer = false;
    return answer;
}

하지만 이런 풀이는 다음과 같은 반례때문에 잘못되었다. (질문게시판 참조)

입력값 〉 ["123", "2345", "23467"]

기댓값 〉 true

즉, 가장 짧은 단어만을 기준으로 파싱하면 위는 234, 234해서 false가 되어버린다. 즉, 최소길이 단어가 접두어임을 보장하지 않는다.

따라서 이 문제는 모든 접두어 길이의 수를 고려해주어야 한다는 점이 핵심이다. 

 

+c++ map은 key와 value를 무조건 정의해주어야 한다. 그래서 별로 의미없는 수를 value로 넣었다. 

3. 문제 해결

수정한 풀이 과정은 다음과 같다.

1. 우선 전화번호부에 있는 모든 값을 map에 넣어준다.

2. 이중 반복문을 돌면서, 모든 접두어 길이의 수를 고려하여 map에 있는지 검사한다. 

 

2번이 핵심이다. 전화번호부 길이는 20을 넘지 않기 때문에 이중반복문을 돌아도 시간초과가 나지 않는다. 

4. 코드

#include <string>
#include <vector>
#include <map>

using namespace std;

bool solution(vector<string> phone_book) {
    bool answer = true;
    map<string, int> m;
    for (int i = 0; i < phone_book.size(); i++)
        m.insert({phone_book[i], phone_book[i].length()});
    for (int i = 0; i < phone_book.size(); i++)
    {
        int length = phone_book[i].length();
        for (int j = 0; j < length; j++)
        {
            if (m.find(phone_book[i].substr(0, j)) != m.end())
            {
                answer = false;
                return (answer);
            }
        }
    }
    return answer;
}