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

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

프로그래머스

 

https://usowelcome.tistory.com/56

99클럽 코테 스터디 5일차 TIL : 전화번호 목록

 

엥 풀어봤던거다!

이번에는 안헤매고 한번에 정렬해서 풀었다..!

근데,,왜,,,해시에 들어가있지?????? 싶어서 다른사람풀이를 열심히 찾아봤다

 

1. 정렬

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool solution(vector<string> phone_book) {
    
    sort(phone_book.begin(), phone_book.end());
    
    int compj = 0;
    for(int i = 1; i<phone_book.size(); i++)
    {
        if(phone_book[i].compare(0, phone_book[compj].size(), phone_book[compj]) == 0)
        {
            // 접두어
            return false;
        }else{
            compj = i;
        }
    }
    
    
    return true;
}

문자열을 사전순으로 정렬됐을 때.. 뒤에 딸린게 많으면 뒷순위로 간다

-> 11911, 1191, 119 (X)

-> 119, 1191, 11911 (O) 이 순서로 정렬됨!! (문자열이니까)

 

그니까 바로 뒤에꺼랑 비교했을 때, (i, i+1) i가 i+1의 접두어가 아니면,,, i를 접두어로 가지는 애는 더이상 없는것!!

i+1과 i+2를 비교한다.

 

이제보니까 난 굳이 compj로 인덱스를 관리했는데 걍 i랑 i+1 비교하는식으로 해도 됐을것같당...

 

2. 해시

set을 활용하는것같다.

일단 모든 전화번호를 set에 넣어둔다

 

그리고 하나하나 비교를 하는데....

-> "11911"의 접두어를 찾는다면

   -> set에서 "1"찾기

   -> set에서 "11"찾기

   -> set에서 "119"찾기

   -> set에서 "1191"찾기

이것들중에 하나라도 찾아지면 접두어가 있는것!!!!! false를 반환한다.

 

해시의 find가 O(1)이라 생각할법한건가..?

 

#include <string>
#include <vector>
#include <unordered_set>

using namespace std;

bool solution(vector<string> phone_book) {
    
    unordered_set<string> set(phone_book.begin(), phone_book.end());
    
    for(int i = 0; i<phone_book.size(); i++)
    {
        for(int j = 1; j<phone_book[i].size(); j++)
        {
            if(set.find(phone_book[i].substr(0, j)) != set.end())
            {
                // 접두어 있음
                return false;
            }
        }
    }
    
    return true;
}

 

효율성도 정렬이 더 좋은데... 참 뭘까..............

 

nlogn과 nm의 차이인가?? 잘 모르게따..