[프로그래머스] 전화번호 목록

문제링크 : https://school.programmers.co.kr/learn/courses/30/lessons/42577

💻 문제 풀이 : C++

🤣 고대의 내가 풀었던 코드 - 시간초과!

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

bool cmp(string a, string b)
{
    if(a.size() < b.size()) return true;
    if(a.size() > b.size()) return false;
    return false;
}

bool solution(vector<string> phone_book) {
    bool answer = true;
    sort(phone_book.begin(), phone_book.end(), cmp);
    for(int i = 0 ; i < phone_book.size() ; i++)
    {
        for(int j = i+1 ; j < phone_book.size() ; j++)
        {
            int flag = 0;
            for(int k = 0 ; k < phone_book[i].size() ; k++)
            {
                if(phone_book[i][k] != phone_book[j][k])
                    break;
                else
                    flag++;
                if(flag == phone_book[i].size())
                    return false;
            }
        }
    }
    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());
 
    //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;
}

⭐ 해쉬를 이용한 풀이법

#include <string>
#include <vector>
#include <unordered_map>
#include <iostream>
using namespace std;
 
bool solution(vector<string> phone_book) {
    bool answer = true;
    unordered_map<string, int> map;
 
    // key : elem, value : 출현 횟수?
    for (auto elem : phone_book)
        map[elem]++;
 
    // phone_book을 탐색
    for (int i = 0; i < phone_book.size(); i++) {
        string number = "";
        // phone_book의 번호 한개씩 탐색        
        for (int j = 0; j < phone_book[i].size(); j++) {
            number += phone_book[i][j];
            // cout << number << " " << map[number] << " " << phone_book[i] << endl;
            // Eureka!!
            if (map[number] && number != phone_book[i])
                return false;
        }
    }
    return answer;
}

출처 : https://foameraserblue.tistory.com/16

💻 문제 풀이 : Python

⭐ 내 풀이

def solution(phone_book):
    dic = {}
    for num in phone_book:
        dic[num] = 1
    
    for num in phone_book:
        my_str = ""
        for i in num:
            my_str += i
            if (dic.get(my_str) != None) & (my_str != num):
                return False
    return True

---

📌 memo