전화번호 목록 (feat. 프로그래머스, 42577번)

전화번호 목록
https://school.programmers.co.kr/learn/courses/30/lessons/42577

프로그래머스

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <string>
#include <vector>
#include <set>
using namespace std;
bool solution(vector<string> phone_book) {
    set<string> tmp;
    for (auto& number : phone_book)
        tmp.insert(number);
    for (auto it1 = tmp.begin(); it1 != tmp.end(); ++it1)
        for (auto it2 = it1; it2 != tmp.end(); ++it2)
            if (it1 != it2)
                if (it2->find(*it1) == 0)
                    return false;
                else
                    break;
    return true;
}
// *&)*@*

 

1. 자료구조 set을 이용하면 string을 오름차순 또는 내림차순 으로 정렬할 수 있습니다.
2. 정렬된 set을 arr[N] 이라고 한다면, arr[0]을 arr[1] ~ arr[N]까지 비교합니다.
3. 만약 arr[1] ~ arr[N]과 비교하여 (string의 find 함수) 찾지 못한다면 arr[0]은 다음 비교를 할 필요가 없습니다. 왜냐하면 arr[1] ~ arr[N]은 정렬되어 있기 때문입니다.
4. 조금 더 설명하자면 arr[1]과 arr[0]과 비교하였을때 그 값이 -1 이라면 정렬된 상태이므로 arr[2]와 arr[0]은 비교하지 않아도 -1 입니다.
5. 따라서 다음 arr[1]과 arr[2] ~ arr[N] 간 비교를 진행합니다.