[C++] 프로그래머스 Level 2 : 전화번호 목록

#include <iostream>
#include <string>
#include <vector>
#include <algorithm> // sort

using namespace std;

bool solution(vector<string> phone_book) {
    bool answer = true;
    
    sort(phone_book.begin(), phone_book.end()); // 빠른 비교를 위한 sort
    
    for(int i = 0; i < phone_book.size() - 1; i++){
        // string find 함수로 해당 문자열 속해있는지 확인할 수 있음
        int cnt = phone_book[i].size();
        // sort를 통해서 바로 다음 친구와 비교만 하면 된다.
        if(phone_book[i] == phone_book[i+1].substr(0, cnt)){
            return false;
        }
    }
    
    return answer;
}

map을 쓰는 해시 문제인데 그냥 비교해서 풀었다.
sort를 이용하면 O(logN)이므로 for문 2개 O(N^2)보다 적은 시간 복잡도를 가진 비교를 할 수 있다.

시간 초과 및 틀린 테스트 케이스 생긴 코드

#include <iostream>
#include <string>
#include <vector>

using namespace std;

bool solution(vector<string> phone_book) {
    bool answer = true;
    
    for(int i = 0; i < phone_book.size(); i++){
        int cnt = phone_book[i].size(); // string size 함수로 구하기 가능
        for(int j = i+1; j < phone_book.size(); j++){
            // substr으로 string 잘라서 비교 가능
            cout << phone_book[i] << " " << phone_book[j].substr(0, cnt) << "\n";
            if(phone_book[i] == phone_book[j].substr(0, cnt)){
                return false;
            }
        }
    }
    
    return answer;
}

for문 2개를 사용하면 정렬되어있지 않아 너무 많은 비교를 해줘야한다. 그래서 아마 틀렸습니다가 나오지 않았을까? 로직은 똑같다.

오늘 배운 C++ 지식

• string의 부분을 잘라 비교하려면 substr을 사용하면 된다.
• string에 해당 요소가 있는지를 확인하려면 find를 사용하면 된다.
• string의 길이를 알고 싶으면 size를 사용하면 된다.