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

 

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

프로그래머스

 

 

해시 문제라서 해시로 풀려고 해 봤는데 잘 모르겠어서 그냥 string으로 풀었다.

정렬하면 가장 작은 문자열이 오름차순으로 정렬되므로 해줬는데,

2중 for문으로 뒷 원소들이 이 문자열을 가지고 있는지 체크해주면서 있으면 return false로 바로 끝내고 아니면 끝나고 return answer(true) 해줬다.

 

bool solution(vector<string> phone_book) {
    bool answer = true;
    sort(phone_book.begin(), phone_book.end());
    
    for(int i=0; i<phone_book.size(); i++){
        string s1 = phone_book[i];
        for(int j=i+1; j<phone_book.size(); j++){
            string s2 = phone_book[j];
            size_t pos = s2.find(s1);
            if(pos == 0) return false;
        }
    }
    return answer;
}

 

따쉬... 날 힘들게 하는 시간 초과 - 아마 2중 for문이 문제였던 거 같다. phone_book 길이가 최대 1,000,000라니 인싸군

 

 

 

---

 

그래서 뭔가 흠.. 문자열이 정렬되는 순서를 출력해봤다.

"119", "97674223", "1995524421" 이면 나는 당연히 119 - 97674223 - 1995524421라고 생각했는데

띠용 119 - 1995524421 - 97674223 였다.

이러면 굳이 2중 for문을 사용하지 않고,, 바로 뒷 놈만 체크하면 되지 않을까? 싶어서 해봤다.

 

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

 

통과~