프로그래머스 42577 - 전화번호 목록 (c++)

프로그래머스 42577 - 전화번호 목록

문제 링크

접근 및 생각

• 우선, vector string을 sort했을 때 어떤 식으로 나열되는지 알아야 문제를 쉽게 풀 수 있었습니다. phone_book의 vector type이 int인 경우와 vector type이 string인 경우의 sort 결과가 다릅니다.

• 입출력 예제에서 준 vector string sort의 결과는 아래와 같습니다.

  

• string은 int와 달리 문자로 취급되므로 사전순으로 나열 됩니다. 사전을 펼쳐서 가 다음에 가나 가 나오듯이, phone_book을 sort하면 119 다음엔 1195524421 이 나옵니다. sort한 vector를 앞 원소와 바로 뒤 원소를 비교하여 접두어가 있는지 없는지를 판단하면 되겠습니다.

• 접두어가 있는지 어떻게 판단하느냐. 저는 string의 substr() 함수를 사용했습니다. substr()은 문자열의 일부분을 문자열로 반환하는 함수로, 파라미터를 1개, 2개를 넣을 수 있습니다.

  • 1개일 경우 : ( 시작위치 ) : 시작위치부터 끝까지의 문자들을 문자열로 반환합니다.

  • 2개일 경우 : ( 시작위치, 개수 ) : 시작위치부터 개수만큼의 문자를 문자열로 반환합니다.

    string s = "ABCDEF";
    string s2 = s.substr(4);      // s2 = "EF"    ( index 4부터 끝까지의 문자열을 반환한다. )
    string s3 = s.substr(1,3);    // s3 = "BCD"   ( index 1부터 3까지의 문자열을 반환한다. )

  • 출처 C++ 라이브러리 - String 클래스 함수 정리|작성자 김랜턴

• 이 점을 활용해서 앞의 원소의 string length만큼 뒤의 원소를 substr한 값을 앞의 원소와 비교합니다. 같다면 return false, 다르다면 다음 원소를 비교합니다. phone_book을 모두 비교해도 return false되지 않았다면, 접두어가 없는 phone_book이므로 return true해주시면 되겠습니다.

코드

#include <bits/stdc++.h>
using namespace std;

bool solution(vector<string> phone_book) {
    sort(phone_book.begin(), phone_book.end());

    // 출력을 위한 코드
    // for(auto k : phone_book){
    //     cout << k << endl;
    // }

    for(int i = 1; i < phone_book.size(); i++){
        string temp = phone_book[i].substr(0, phone_book[i - 1].length());
        if(temp == phone_book[i - 1])
            return false;
    }
    return true;
}

채점 결과