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

 

해시를 이용했다. 여기서 오늘 알고가야 할 내용은 substr() 함수이다.

 

substr()함수는 이렇게 사용한다. substr(시작인덱스, 갯수)

 

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

using namespace std;

int cmp(string& a, string& b) {
    
    return a.length() < b.length();
}

bool solution(vector<string> phone_book) {
    
    map<string, int> m;
    
    int size = 0;
    
    sort(phone_book.begin(), phone_book.end(), cmp);
    
    for(auto a : phone_book) {
        size = a.length();
        
        for(int i = 1; i <= size; i++) {
            
            if(m[a.substr(0, i)] > 0) // substr(시작인덱스, 갯수)
                return false;
        }
        
        m[a]++;
    }
    
    return true;
}

 

 

 

다른 사람의 풀이를 보고 경악했다.

["12", "123", "1235", "567", "88"]

를 sort() 하면 아래와 같은 결과를 얻게 되는데

["12", "123", "1235", "567", "88"]

이 특징을 이용해서, 앞이랑 뒤만 비교한 것이다.

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

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

    sort(phoneBook.begin(), phoneBook.end());

    for ( int i = 0 ; i < phoneBook.size() - 1 ; i++ )
    {
        if ( phoneBook[i] == phoneBook[i+1].substr(0, phoneBook[i].size()) )
        {
            answer = false;
            break;
        }
    }

    return answer;
}