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

*제출 코드

#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++){
        for(int j=i-1; j>=0; j--){
            if(phone_book[i].find(phone_book[j]) == 0)
                return false;
        }
    }
    
    return answer;
}

 

*review

0. 전체적인 아이디어:
  string 배열을 오름차순으로 정렬하고, 특정 원소가 특정 원소보다 앞쪽에 있는 원소를 접두사로 가지는지 확인한다.

 

 

1. 왜 특정 원소보다 앞쪽에 위치한 원소만 확인할까?

 

  접두사가 되려면 문자열의 길이가 어떤 문자열보다 짧거나 같아야 하는데,

  string배열을 오름차순으로 정렬하면 특정 원소 앞에는 그 원소보다 길이가 짧거나 같은 문자열들만 위치하게 된다.

 

  고로, 정렬 후 특정 원소에 대해 앞에 있는 원소들만 검사하면 접두사가 있는지 확인할 수 있다.

 

 

2. 접두사인지 검사하는 방법? c++ string클래스의 find() 함수를 이용!

 

  s.find("aa") => 스트링 s에 "aa"라는 문자열이 있으면, 일치하는 부분의 첫 번째 인덱스를 반환한다.

  고로, 접두사일 경우에는 0을 반환하게 된다.

  s.find("aa") == 0 이 true라면 aa는 스트링 s의 접두사이다.

 

 -string 클래스 함수 참고 

[C++] string 클래스, 문자열에 대해서 (총정리)

3. 더 나은 방법?

본인은 접두사인지 검사할 때 특정 원소보다 앞에 위치한 모든 원소들을 검사했는데,

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

 

다른 풀이들을 보니 앞쪽의 모든 원소들이 아니라, 바로 앞에 있는 원소만 접두사인지 검사하면 더 효율적이게 문제를 풀 수 있었다.

예를 들어 정렬된 배열 ["118", "119", "1194", "1195"]이 있을 때, "1194"는 바로 앞의 원소인 "119"만 검사하면 접두사인지 알 수 있다.

 

string문자열의 비교는

1. 맨 처음 인덱스부터 비교하다가 다른 문자가 나오게 되면, 그 다른 문자가 더 큰 문자열을 크다고 판단한다.

2. 맨 처음 인덱스부터 비교하다가 어느 한 문자열이 끝나버리면, 길이가 더 긴 문자열을 크다고 판단한다.

 

따라서 "1194"바로 앞에는 1. 같은 접두사를 가졌거나  2.길이가 더 짧은 문자열이 있을 것이다.

이 중 2.길이가 더 짧은 문자열이 있다면, 그것이 바로 지금 문자열의 접두사인 것이다.

 

"1195"의 경우는 "119"라는 접두사가 있지만 "1194"만 접두사인지 아닌지 판단한다.

하지만, 전체 배열에서 접두사가 있는지 없는지만 판단하는 해당 문제에서는 고려할 필요가 없다. 

이미 "1194"의 경우에서 "119"라는 접두사가 있음을 판단하고 return false를 했기에, 바로 앞에는 접두사가 없는 "1195"의 경우는 고려할 필요가 없다.