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

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

프로그래머스

 

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

using namespace std;

bool solution(vector<string> phone_book) {
    bool answer = true;
    
    unordered_map<string,bool>um;
    for(int i=0;i<phone_book.size();i++)
        um.insert({phone_book[i],true});
    
    for(int i=0;i<phone_book.size();i++)
    {
        string cur = phone_book[i];
        string temp="";
        for(int j=0;j<cur.length();j++)
        {
            temp+=cur[j];
            if(um[temp]&&cur!=temp)
                return false;
        }
    }
    
    return answer;
}

전화번호 목록이 주어지면 어떤 한번호가 다른 번호의 접두어로 들어가는지 여부를 판단해서 리턴해주는 문제이다.

ex) 1234, 1234567 이라면 두번째번호의 접두어에 1234가 해당되므로 false리턴이다. 

 

해시맵을 이용해 푸는 것이 효율적인 문제이다. 값을 검색하는데에 있어서 해시가 O(1)의 성능을 보여주기 때문이다. 

따라서 map중에서 해시맵을 사용하는 unordered_map 을 사용했다. 

미리 해시테이블에 현재 전화번호 목록을 전부 저장해둔다. 

 

그리고 for문을 돌면서 각 전화번호를 기준으로 한글자씩 string을 만들어서 해시테이블에 있는지 비교를 한다. 

ex) phone_book[i] = "1568" 일 때, 

1, 15, 156 이 테이블에 있는지 확인하는 것이다. 

 

조건 중 cur!= temp 는 1568은 당연히 테이블에 있을 것이므로 제외한다. 

1568이 접두어로 적용되는 번호가 있다면 다른 인덱스에서 걸리기 때문이다. 

 

처음에는 이중포문으로 string 함수인 find와 substr을 이용해 제출해보았다. 

그러나 효율성에서 2개가 틀렸다. 알아보니 find는 O(n) ,  substr은 O(n*m) 의 성능을 가지므로

각각 O(n^3), O(n^4) 까지 보여주기 때문에 효율성에서 실패가 떴다고 생각한다. 

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool solution(vector<string> phone_book) {
    bool answer = true;
    
    sort(phone_book.begin(),phone_book.end());
    
    for(int i=0;i<phone_book.size()-1;i++)
    {
        for(int j=i+1;j<phone_book.size();j++)
        {
        	// find를 쓴 경우
            if(phone_book[j].find(phone_book[i])==0)
                return false;
            // substr을 쓴 경우
 			if(phone_book[j].substr(0,phone_book[i].length())==phone_book[i])
                return false;
        }
    }
    
    return answer;
}

 

 

 

줄이려면 해시테이블을 써야겠다는 생각에 unorded_map에 string,unordered_set 으로 string의 모든 부분문자열 즉, 정답코드에서 하나씩 더하던 것을 미리 다 해놓고 for문으로 확인해야겠다고 생각했다. 

하지만 결국 효율성 2개가 실패가 떴다. 

 

정답 코드는 이 아이디어를 반대로 다 만들어놓지 않고 주어진 번호들을 테이블에 넣어놓고 

번호들의 숫자를 한개씩 추가하면서 테이블에 있는지 비교했다. 

 

검색이 많이 필요할때는 해시맵을 사용하는 unordered_map과 unordered_set을 사용해야한다는 것을 배웠다.