CodingTest Practice/Programmers

프로그래머스 : 전화번호 목록 (C++, Lv.2, 해시)

몽땅마니아(MDD) 2022. 5. 20. 15:31

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

 

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

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조

programmers.co.kr

 

소스코드 

아래 실패 코드를 보면서 시간복잡도도 완전히 오버되고 로직이 틀렸음을 깨닫고 완전히 새로 짰다.

그 와중에 두 string이 같은지 확인하는게 strcmp 인줄 알고 계속 왜 틀렸나 했더니 그냥 == 쓰거나 compare를 써야 하는 것이었다.

string 에 대해 제대로 알아야 할 것 같다. https://blockdmask.tistory.com/338

 소스 코드

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


using namespace std;

bool solution(vector<string> phone_book) {
    
    unordered_map <string, int> m;
    // 먼저 해시맵에 모든 전화번호 삽입
    for(string s : phone_book) m.insert(make_pair(s,1));
    string cmp = "";
    
    //모든 전화번호 탐색
    for(string s : phone_book) {
        cmp = "";
        //해당 전화번호를 한글자씩 더해서 붙여진 번호를 키로 같는 맵이 있는지 확인
        for(char c : s) {
            cmp = cmp + c;
            // s== cmp  과 s.compare(cmp) 은 같음,
            if(s == cmp) break;
            if(m.count(cmp)) return false;
        }
    }
    return true;
}

 


 실패코드

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

using namespace std;

bool solution(vector<string> phone_book) {
    
    unordered_map <string, int> m;
    
    for(string s : phone_book) {
        string cmp = "";
        for(char c : s) {
            cmp = cmp + c;
            if(m.count(cmp)) return false;
        }
        m.insert(make_pair(s,1));
    }
    return true;
}