전화번호 목록/C++

프로그래머스

해시 분류에 속해있는 문제인만큼 해시를 사용해서 문자를 하나씩 받아 비교하는 방식으로 풀이하였다.

처음 코드 실행 시 테스트 케이스 2번이 오답이 나와서 확인해보니 문자를 비교하는 부분에서 현재 문자열과 같을 때는 제외하는 코드를 작성하지 않아 생긴 문제였다.

if문에 tmp != phone_book[i]가 빠졌다.

풀이방법

1. string형을 key로 int형을 value로 가지는 unordered_map 변수를 선언한다.

2. 각 전화번호들을 key로 하고 value는 1을 값으로 가지도록 한다.

3. string형 tmp에 phone_book[i]의 문자를 하나씩 더해주며 tmp가 phone_book[i]와 같지 않고, unordered_m[tmp]의 value가 1이면 다른 번호가 현재 번호의 접두어로 쓰인것이므로 false를 리턴한다.

4. 반복문이 완전히 끝났다면 한 번호가 다른 번호의 접두어로 쓰인 경우가 없으므로 true를 리턴한다.

 

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

using namespace std;

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