99클럽 코테 스터디 5일차 TIL : 전화번호 목록

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

프로그래머스

흠,, 간단해보였는데 이런저런 어려움이 조금 있었다

실행해온것들을 보면서 왜 내가 빡대가리인지 알아보도록 하겠다!

---

[첫번째 시도]

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

using namespace std;

bool solution(vector<string> phone_book) {
    
    for(int i = 0; i<phone_book.size();i++){
        phone_book[i].erase(remove(phone_book[i].begin(), phone_book[i].end(), ' '), phone_book[i].end());
    }
    
    for(int i = 0; i<phone_book.size();i++){
        for(int j = i+1; j<phone_book.size(); j++){
            if(phone_book[i].find(phone_book[j]) != string::npos){
                // find
                //cout << phone_book[i]<<phone_book[j]<<endl;
                return false;
            }else if(phone_book[j].find(phone_book[i]) != string::npos){
                return false;
            }
        }
    }
    
    return true;
}

문제이해를 이상하게했다.

일단, 문제 윗부분만 보고 띄어쓰기가 포함되어 string에 들어간다고 착각했다. 그래서 첫번째 반복으로 띄어쓰기를 없애주는 처리를 해주었는데, 필요가 없었다...!

그리고 앞부분이 똑같은 거였는데, 그냥 포함만 되면 된다고 생각하여 find를 사용했다...ㅋ....

아무튼 이거때문에 탈락,,,

 

---

[두번째 시도]

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

using namespace std;

bool solution(vector<string> phone_book) {
    
    for(int i = 0; i<phone_book.size();i++){
        phone_book[i].erase(remove(phone_book[i].begin(), phone_book[i].end(), ' '), phone_book[i].end());
    }
    
    for(int i = 0; i<phone_book.size();i++){
        for(int j = i+1; j<phone_book.size(); j++){
            bool flag = true;
            if(phone_book[i].size() <= phone_book[j].size()){
                if(!phone_book[i].compare(phone_book[j].substr(0, phone_book[i].size()))){
                    // 같음
                    return false;
                }
            }
            if(phone_book[i].size() > phone_book[j].size()){
                if(!phone_book[j].compare(phone_book[i].substr(0, phone_book[j].size()))){
                    // 같음
                    return false;
                }
                
            }
        }
    }
    
    return true;
}

이제 문제를 이해했다!

앞부분만 같을때만 false를 반환해준다.

1234, 123 -> 앞부분이 같으므로 false

1234, 234 -> 앞부분이 같지 않으므로 true

이런식으로 처리된다.

 

근데!! 또 망할 효율성테스트에서 걸렸다.

사실 작성하면서도 for가 2개나 중첩되어서 걱정되긴 했는데...^^....

 

그래서 이래저래 고민을 많이해봤다.

for한번으로 해결할 수 없을까??

그러기 위해서는 phone_book을 어떠한 기준으로 정렬할 필요가 있다고 생각했다.

 

이 때, string을 그냥 sort하면 사전순으로 정렬된다는것을 알게되었다!

 

1, 2, 34, 22, 87, 102, 10004, 2222

-> 1, 102, 10004, 2, 22, 2222, 34, 87

이렇게 정렬된다.

그러면, 일단 맨 앞글자가 같은애들끼리, 그 다음글자가 같은애들끼리 모여있게된다

== 앞뒤만 비교하면 된다!

 

---

[세번째 시도]

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

using namespace std;

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

이렇게 sort를 이용해 phone_book을 한번 정렬해주었다.

그리고 for 한번만 이용해서 자기자신과 바로 뒷 번호만 비교를 해주고,

중간에 조건에 맞는게 검출되면 바로 return하도록 해주었다.

---

흠... 역시 효율성테스트는,,,, 어렵구나!