[알고리즘문제] 프로그래머스 전화번호 목록

 

programmers.co.kr/learn/courses/30/lessons/42577

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

 

첫번째 풀이

배열 내 한 원소를 기준으로 다른 원소와의 계산을 위하여 2중반복문으로 문제를 풀었다.

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

using namespace std;

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

    for (int i = 0; i < phone_book.size(); i++) {
        for (int j = i+1; j < phone_book.size(); j++) {
            if (i != j && i < j) {
                if(phone_book[i].length() <= phone_book[j].length()){
                    if (phone_book[j].find(phone_book[i]) != string::npos && phone_book[j].find(phone_book[i]) == 0)
                        return false;
                }
                else {
                    if (phone_book[i].find(phone_book[j]) != string::npos && phone_book[i].find(phone_book[j]) == 0)
                        return false;
                }
            }
        }
    }

    return answer;
}

위의 문제는 효율성 검사에서 실패가 되었다.

2중 for문을 사용하여 효율성이 떨어진 것으로 생각되었고 아래의 코드로 변경하여 제출하니 효율성 체크도 통과하였다.

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

using namespace std;

bool solution(vector<string> phone_book) {
    sort(phone_book.begin(), phone_book.end());
    for (int i = 0; i < phone_book.size(); i++) {
        if (i == phone_book.size() - 1) break;
        if (phone_book[i + 1].find(phone_book[i]) != string::npos && phone_book[i + 1].find(phone_book[i]) == 0) return false;
    }
    return true;
}

 

배열을 sorting할 경우 사전적으로 정렬이 되며, 배열 내 접두어가 있을 경우 어떤 원소는 다음 원소의 접두어가 되도록 정렬이 된다. 그래서 인접한 원소만 비교하면 되므로 반복문을 한번만 사용하면 되고 2중 반복문을 사용할때에 비하여 코드의 효율성이 높아진다.