[C++] 프로그래머스 코딩테스트 연습 - 전화번호 목록

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

알고리즘 헤더에 있는 sort를 이용하여 쉽게 구현하였다.

먼저 sort를 하게되면 숫자 순서대로 정렬이 되고 문제에서 요구하는 접두어의 경우 반드시 인접한 위치에 정렬되게 된다.

예를 들어서 [12345, 332, 123]을 정렬하게 되면 [123, 12345, 332] 이런 식으로 정렬된다는 뜻이다.

그리고 여기서 한가지 알 수 있는 사실은 정렬된 이후 접두어에 해당하는 숫자는 무조건 앞에 나오게 된다.

따라서, 모든 배열의 원소를 완전탐색하여 현재의 위치와 현재의 위치 직전의 문자열을 서로 비교하여 string 클래스의 find() 함수를 사용하여 일치하는 문자열이 나오면 정답으로 출력하면 된다.

만약, find()로 일치하는 문자열이 나오지 않았을 경우 return 값으로 string::npos가 iterator로 반환된다.

#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());
    for(int i = 1; i < phone_book.size(); i++){
        if(phone_book[i].find(phone_book[i-1]) != string::npos){
            answer = false;
            break;
        }
    }
    return answer;
}

string 클래스의 find()를 사용하지 않고 문자 하나 하나를 일일이 비교하는 방법으로 아래와 같이 풀 수도 있다. 시간복잡도 면에서는 차이가 나지는 않을 것이다.

다만, 문자를 일일이 비교할 경우 반드시 [이전문자의 길이] <= 다음문자의 길이]가 성립할 수  있는 case만 정답의 조건이 되므로 if문으로 11번째 줄과 같이 처리해주었다.

#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());
    for(int i = 1; i < phone_book.size(); i++){
        if(phone_book[i].size() < phone_book[i-1].size())
            continue;
        bool chk = false;
        for(int j = 0; j < phone_book[i-1].size(); j++){
            if(phone_book[i][j] != phone_book[i-1][j]){
                chk = true;
                break;
            }
        }
        if(!chk){
            answer = false;
            break;
        }
    }
    return answer;
}