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

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

풀이

알고리즘 분류가 해시로 되어 있어 해시로 푸는 방법을 찾다가 결국 다른 방법으로 풀었다.
우선 길이가 짧은 순서대로 phone_book 벡터를 정렬한 다음에, 이중포문과 find를 사용해서 모든 전화번호 목록을 비교해줬다.
더 나은 풀이가 있을 것 같은데 생각나는 방법이 이것밖에 없어서 풀어봤는데 맞았다...!
해시나 다른 방법으로 푼 코드도 꼭 확인해줘야겠다.

(8월 24일 업데이트 - 다른 풀이 공부하기)

1. sort - 단어를 사전 순서대로 정렬하여 인접한 단어와 비교해주기

2. 해시 사용하기

※ 잠깐! vector 정렬 다시 공부하기

#include <algorithm>에 sort()을 이용하면 벡터를 쉽게 정렬할 수 있는데, 이번에는 compare함수를 직접 만드는 방법을 공부해보려고 한다.
이 문제에서 string의 길이로 정렬을 해주기 위해 compare함수를 만들었다.(오름차순)

bool cmp(string& s1, string& s2){
    return s1.size() < s2.size();
}

sort(phone_book.begin(), phone_book.end(), cmp);

// [12,123,1235,567,88] -> [12,88,123,567,1235]

반성

• 문제를 풀 때 내가 처음 생각한 방법에 자신감이 부족하다.
• 더 나은 방법을 찾다가 시간을 많이 소모한다.
• 다음에 문제를 풀 때는 처음에 생각했던 방법으로 그대로 밀고 나가자

코드

내 풀이 코드

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

bool cmp(string& s1, string& s2){
    return s1.size() < s2.size();
}
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++){
            if(phone_book[j].find(phone_book[i]) == 0) return false;
        }
    }
    return answer;
}

다른 풀이 - 1

#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());
    // [12,123,1235,567,88]
    
    for(int i = 0 ; i < phone_book.size() - 1 ; i++){
        if(phone_book[i+1].find(phone_book[i]) == 0) return false;
    }
    return answer;
}

다른 풀이 - 2

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

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