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

문제 풀이

#include <string>
#include <algorithm>
#include <vector>

using namespace std;

bool solution(vector<string> phone_book) {
    bool answer = true;
    
    // 배열을 정렬. string 형태이므로 크기순이 아닌 사전순으로 정렬된다.
    sort(phone_book.begin(), phone_book.end());
    
    // 맨 앞의 원소를 접두어로 삼는다
    string chk = phone_book[0];
	for (int i = 1; i < phone_book.size(); i++) {
		if (phone_book[i].substr(0, chk.size()) == chk)	
			answer = false;
	}
    
    return answer;
}

 이렇게 풀어도 전부 통과가 나오는데, 가만 생각해보면 {"12", "23", "234"} 등의 배열과 같이 첫 번째 원소가 아니라 그 이후의 원소가 접두어가 되는 경우가 생길 수 있다. 

 

 해서 다른 사람들이 푼 코드를 보면

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

bool solution(vector<string> phoneBook) {
    bool answer = true;

    sort(phoneBook.begin(), phoneBook.end());

    for (int i = 0; i < phoneBook.size() - 1; i++ ) {
        if ( phoneBook[i] == phoneBook[i+1].substr(0, phoneBook[i].size())) {
            answer = false;
            break;
        }
    }

    return answer;
}

 이처럼 맨 앞을 기점삼는 것이 아니라 맨 앞부터 2개씩 쌍을 묶어 비교하는 방법을 사용하고 있음을 할 수 있다. 이것이 가능한 이유는 phoneBook 배열이 숫자가 아닌 문자열로 이루어져 있기 때문이다. 크기가 아닌 사전순으로 정렬되기 때문.

 

 

 

문제 링크

programmers.co.kr/learn/courses/30/lessons/42577programmers.co.kr/learn/courses/30/lessons/42577?language=cpp

코딩테스트 연습 - 전화번호 목록