[프로그래머스] Level 2. 전화번호 목록

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

프로그래머스

 

해결 방법 1 (실패)

문제 자체는 간단한데, 포인트는 어떻게하면 효율적으로 찾을 수 있는지이다. 

• 길이 순서대로 정렬한다.
• 앞에있는것이 무조건 접두사가 될테니, 자신 기준 뒤에있는 애들을 검사해본다.

이렇게 풀었는데, 효율성 검사에서 2개 실패를 받았다.

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

bool compare(string a, string b){return a.size() < b.size();}
bool solution(vector<string> phone_book) {
    
    sort(phone_book.begin(), phone_book.end(), compare);
    for(int i=0; i<phone_book.size(); i++){
        for(int j=i+1; j<phone_book.size(); j++){
            string str = phone_book[j].substr(0,phone_book[i].size());
            if(phone_book[i] ==str) return false;
        }
    }
    return true;
}

 

해결 방법 2 (실패)

그래서 생각한 것이, 작은 배열 여러개(10개)로 쪼개서, 검사횟수를 1/10로 줄일 수 있지 않을까 하는 생각이었다.

전화번호가 N으로 시작하는 번호들끼리 모아서 그 리스트 안에서만 검사를 하는것이다. 이것도 효율성 검사에서 2개를 틀렸다(효율점 8점)(

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

bool compare(string a, string b){return a.size() < b.size();}
bool solution(vector<string> phone_book) {
    
    vector<vector<string>> nums(10);
    
    for(int i=0; i<phone_book.size(); i++){
        int idx = phone_book[i][0]-'0';    
        nums[idx].push_back(phone_book[i]);
    }
    
    for(int i=0;i<nums.size();i++){
        auto& arr = nums[i]; //첫번째숫자 i인 번호들의 모음
        sort(arr.begin(),arr.end(),compare);
        for(int j =0 ; j<arr.size(); j++){
            for(int k= j+1; k<arr.size(); k++){
                string str = arr[k].substr(0,arr[j].size());
                if(arr[j] == str) return false;
            }
        }
    }
  
    return true;
}

 

해결 방법 3 (실패)

작은배열 20개로 쪼개서, 길이가 N인 문자열을 배열 N번째에 넣는다. 즉, 길이가 동일한 애들끼리 배열로 모은 뒤, 자신보다 길이가 긴 애들만 검사를 하는것은 어떤가? > 효율성 검사 1개 실패했다(효율성 12점)

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

bool compare(string a, string b){return a.size() < b.size();}
bool solution(vector<string> phone_book) {
    
    vector<vector<string>> n(21);
    
    //길이가 N인 번호를 nums[N] 에 넣음.
    //자신과 사이즈가 같거나 작으면 검사하지 않아도 됨.
    for(int i=0; i<phone_book.size(); i++){
        n[phone_book[i].size()].push_back(phone_book[i]);
    }
    
    for(int sa = 1; sa <n.size(); sa++){ //small array
        for(int si = 0; si<n[sa].size(); si ++){ //per item in small arr
            for(int ba = sa+1; ba <n.size(); ba++){ //big array
                for(int bi = 0; bi < n[ba].size(); bi++){
                    string str = n[ba][bi].substr(0,n[sa][si].size());
                    if(n[sa][si] == str) return false;
                }
            }    
        }
        
    }
  
    return true;
}

 

해결 방법 4 (성공)

그냥 사전순으로 정렬하고, 내 다음아이템만 검사하면 되는거였다 흑흑.. ㅜㅜㅜ   123 과 12345 가 있다면 무조건 두개는 붙어있을테니까......

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

bool solution(vector<string> phone_book) {
    // 1. 전화번호 목록을 사전순으로 정렬
    sort(phone_book.begin(), phone_book.end());

    // 2. 정렬된 상태에서 인접한 두 번호를 비교
    for (int i = 0; i < phone_book.size() - 1; i++) {
        // 현재 번호가 다음 번호의 접두어인지 확인
        if (phone_book[i + 1].substr(0, phone_book[i].size()) == phone_book[i]) {
            return false; // 접두어 관계가 있으면 false 반환
        }
    }

    return true; // 접두어 관계가 없으면 true 반환
}