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

문제출처 :

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

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

 

해시로 푸는 방식과 정렬로 푸는 방식 모두 통과됩니다. 두 코드 모두를 첨부합니다.

하지만 이 문제에서 phone_book의 길이가 1이상 1000000 이하인 것은 문제의도가 시간복잡도라는 걸 알 수 있습니다.

따라서 해시로 푸는 것을 권장합니다.

 

먼저 정렬 후 벡터로 푸는 코드입니다.

한 번호가 다른 번호 앞부분과 완전히 일치해야 합니다.

정렬하면 사전 순으로 정렬되기 때문에 현재 원소의 옆 원소만 접두어가 같은 지 체크하면 됩니다.

즉, 앞부분과 비교하면서 하나라도 다르면 for문을 빠져나옵니다.

 

[주석없는 코드]

 

#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());
    int l;
    for(int i=0; i<phone_book.size()-1;i++){
        string str1 = phone_book[i];
        string str2 = phone_book[i+1];
        string st;
        if(str1.length()<=str2.length())
            l = str1.length();
        else
            l=str2.length();
        bool same=true;
        for(int j=0; j<l;j++){
            if(str1[j]-'0'!=str2[j]-'0'){
                same=false;
                break;
            }
        }
        if(same){
            answer = false;
            break;
        }
    }
    
    return answer;
}

[주석 있는 코드]

#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());//사전순서(숫자크기순x)
    int l;
    for(int i=0; i<phone_book.size()-1;i++){
        string str1 = phone_book[i];
        string str2 = phone_book[i+1];
        string st;
        if(str1.length()<=str2.length())
            l = str1.length();
        else
            l=str2.length();
        bool same=true;//다른 문자가 하나라도 있으면 false될거야
        for(int j=0; j<l;j++){
            if(str1[j]-'0'!=str2[j]-'0'){//하나라도 다르면
                same=false;
                break;
            }
        }
        if(same){//접두어 같은문자가 있다면
            answer = false;
            break;
        }
    }
    
    return answer;
}

 

이번엔 해시로 푸는 코드입니다.

 

전화번호 목록에 있는 경우 먼저 1로 value를 초기화하고, 각 번호별 부분문자열이 해시 키에 존재하는 지 확인합니다.

확인하는 방식은 find함수를 활용해도 되지만 그냥 key의 value를 탐색해도 됩니다.

unordered_map은 없는 key에 대한 조건문에서 그 key를 넣으면서 value를 0으로 초기화하고, 저는 사전에 등록한 key의 value를 1로 해 주었기 때문에 find함수를 사용하지 않고 key를 식별할 수 있습니다.

 

unordered_map의 '자동 key-value 초기화' 등의 특징을 잘 모르시는 분은 맨 아래 첨부한 링크를 통해 포스팅을 참고하세요.

 

[주석없는 코드]

#include <string>
#include <vector>
#include <unordered_map>
using namespace std;

bool solution(vector<string> phone_book) {
    bool answer=true;
    unordered_map<string, int>m;
    for(string phone : phone_book){
        m[phone] = 1;
    }
    for(string phone: phone_book){
        for(int i=1; i<phone.size();i++){
            if(m[phone.substr(0,i)] == 1)
                answer = false;
        }
    }
    return answer;
}

 

[주석 있는 코드]

#include <string>
#include <vector>
#include <unordered_map>
using namespace std;

bool solution(vector<string> phone_book) {
    bool answer=true;
    unordered_map<string, int>m;
    for(string phone : phone_book){
        m[phone] = 1; // phone_book에 존재하는 번호면 value를 1로 함
    }
    for(string phone: phone_book){//모든 번호에 대해
        for(int i=1; i<phone.size();i++){//각 부분문자열이 번호목록에 존재하는지 확인
            //여기서 없는 key라면 value=0으로 초기화 됨, 우린 value가 1인 걸 찾으므로  그래도 상관없다.
            if(m[phone.substr(0,i)] == 1)
                answer = false;
        }
    }
    return answer;
}

 

* unordered_map의 '자동 key-value 초기화' 등의 특징을 설명해 놓은 포스팅입니다.

eocoding.tistory.com/7

[프로그래머스 해시] 완주하지 못한 선수 - C++