[프로그래머스 LV 2] 전화번호 목록 C++ (해시 풀이법 포함)

programmers.co.kr/learn/courses/30/lessons/42577

코딩테스트 연습 - 전화번호 목록

프로그래머스 해사 문제를 보고있는데

아무리생각해도 정렬이 더 쉽다는 생각을 지울수가없다..

 

일단 정렬로 문제를 풀었고

해쉬는 그 후에 다른 분의 풀이를 참고해서 다시 풀었다.

일단 해시 라는 개념을 가지고 가는게 중요하다 생각해서 카테고리에 맞는 풀이법으로 풀어보자는 느낌

 

1. 정렬풀이법

일단 정렬을 통해 최대한 비슷한 녀석들끼리 한 곳에 묶어줍니다

i번째 친구와 i+1번쨰 친구의 값을

i번의 사이즈 만큼 비교해서 만약 같으면 false반환. 단순한 풀이법입니다.

 

2. 해시풀이법 

일단 맵에 전화번호부에 있는 값을 key로 넣고 value 를 올려줍니다.

그 후 반복문을 통해 값을 앞에서부터 하나씩 추가하며

혹시 그 값이 맵의 key에 있나 탐색해줍니다.

 

만약 key에 있다면 동일한 번호가 아니라는것만 확인해주면 됩니다.

 

//////////////////////////////////////////////////////////////////////////

 

1. 정렬풀이법

#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());
 
    //i+1까지만 비교해도되는게
    //i+1에도 없으면 그 뒤에는 더더욱 없습니다. 왜냐? 정렬을 했기 때문에
    for (int i = 0; i < phone_book.size() - 1; i++) 
        if(phone_book[i]==phone_book[i+1].substr(0,phone_book[i].size()))
            return false;    
    
    return answer;
}

 

2. 해시풀이법

#include <string>
#include <vector>
#include <unordered_map>
using namespace std;
 
bool solution(vector<string> phone_book) {
    bool answer = true;
    unordered_map<string, int> map;
 
    for (auto elem : phone_book)
        map[elem]++;
 
    for (int i = 0; i < phone_book.size(); i++) {
        string number = "";
        //앞에서부터 한개씩 추가하며 해시맵에 있는지 탐색합니다.        
        for (int j = 0; j < phone_book[i].size(); j++) {
            number += phone_book[i][j];
            if (map[number] && number != phone_book[i])
                return false;
        }
    }
    return answer;
}