[C++] 전화번호 목록

처음 떠오른 방법은 2중 반복문으로 문자열을 비교하는 방법이었는데, 보나마나 시간초과가 뜰 것이라 패스했다

다음으로 떠올린 방법은, 주어진 값들을 sort해서 인근값이랑 비교하기. 1중 반복문을 사용한다.

bool solution(vector<string> phone_book) {
    sort(phone_book.begin(),phone_book.end());
    for(int i = 0; i < phone_book.size()-1; i++) {
        int m = min(phone_book[i].size(),phone_book[i+1].size());
        if(phone_book[i].substr(0,m) == phone_book[i+1].substr(0,m))
            return false;
    }
    return true;
}

phone_book을 정렬하고 두 문자열 길이의 최소값으로 substr로 잘라서 비교하는 방식.

생각해보니, 119 1195524421 문자열의 sort에서는 무조건 119, 1195524421 으로 길이가 긴 놈이 뒤로 가기 때문에

bool solution(vector<string> phone_book) {
    sort(phone_book.begin(),phone_book.end());
    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 true;
}

이렇게까지 줄일 수는 있겠다.

 

다른 방법으로 풀어보기

1. substr 대신 find 사용하기

    for(int i = 0; i < phone_book.size()-1; i++) {
        if(phone_book[i+1].find(phone_book[i]) == 0)
            return false;
    }

그냥 find 함수는 반환값이 시작 index이기 때문에, find로 찾아낸 경우 index가 0이면 false를 출력하게끔 했다.

find가 substr보다 빠르다는 말이 있어서 써봤긴 한데, 결과는 같았다.

 

2. 해시테이블 활용하기

해시 문제에 있으니까... 나는 솔직히 그냥 문제 접한 상황에서 해시 생각은 떠올리지도 못했을 것 같은데ㅋㅋㅋ

세번째 입출력 예제를 예로 들어서,

12	1
123	1
1235	1
567	1
88	1

이렇게 해시 테이블을 생성하고, 각 값의 부분문자열이 있는지를 하나씩 검사하는 것. index는 사용되지 않는다.

예를들어, 1235의 경우 1, 12, 123이 해시테이블 내에 존재하는지 검사한다는 얘기이다.

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

using namespace std;

bool solution(vector<string> phone_book) {
    unordered_map<string,int> map;
    for(string ele : phone_book) {
        map[ele] = 1;
    }
    
    for(int i = 0; i < phone_book.size(); i++) {    //모든 전화번호에 대해
        string checkString = "";
        for(int j = 0; j <phone_book[i].size()-1;j++) {
            checkString += phone_book[i][j];
            if(map.count(checkString))
                return false;
        }
    }
    return true;
}

전화번호 길이가 20자리여서 이중 반복문 써도 괜찮은걸까..