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

(5/18) - X 어엄청 오래 걸려서 풀었음

(5/19) - O

https://school.programmers.co.kr/learn/courses/30/lessons/42577

프로그래머스

 

 

방법 1. binary_search

phone_book의 원소를 꺼내서, 그 원소를 substr()로 한 글자씩 조각내면서 (1234라면 1, 12, 123으로. 중복된 원소가 없다고 했으니 1234는 제외), Binary_Search()로 phone_book에 존재하는지 검사한다. phone_book의 원소 처음부터 끝까지 이렇게 검사한다.

 

bool solution(vector<string> phone_book) {
    bool answer = true;
    sort(phone_book.begin(), phone_book.end());
    for (string& s : phone_book) {
        int st_len = s.length();
        string des = s;
        for (int i = 1; i < st_len; i++) {
            // des의 접두어 찾기
            if (binary_search(phone_book.begin(), phone_book.end(), des.substr(0, i))) {
                return false;
            }
        }
    }

    return answer;
}

 

 

방법 2. map::find

vector에 담겨 있던 phone_book을 map 컨테이너에 옮긴 다음, 1번에서 했던 것처럼 조각 낸 string들을 map::find를 통해서 찾는다.

 

bool solution(vector<string> phone_book) {
    bool answer = true;
    map<string, int> m;

    for (string& s : phone_book) {
        m.insert({ s, 0 });
    }

    for (auto& p : m) {
        int len = p.first.length();
        for (int i = 1; i < len; i++) {
            if (m.find(p.first.substr(0, i)) != m.end()) {
                return false;
            }
        }
    }

    return answer;
}

 

 

결론

모든 테스트 케이스에서 속도와 메모리 차이가 크지 않았다. 그런데 효율성 테스트 3, 4번에서 map::find가 속도와 메모리 측면에서 조금 더 비효율적이었다.