Programmers ] Level 2 - 전화번호 목록

 

2021 03 04 이전 정답코드

 

* 이 문제를 풀 때, 주의해야 하는 점은

  "어떤 번호가 다른 번호의 접두어인 경우"라는 것입니다.

  즉 테스트 케이스가  ["12388", "88"]인 경우는 접두사인 경우가 없어 답은 true가 됩니다.

 

* 문제를 풀 때, string STL의 find( )함수를 사용했습니다.

 find함수는 인덱스 0부터 일치하는 문자를 찾습니다.

 해당 일치하는 문자가 있을 경우, 시작 인덱스를 출력합니다.

예시

...효율성 테스트 통과 X 코드

#include <string>
#include <vector>

using namespace std;

bool solution(vector<string> phone_book) {
    bool answer = true;
    string tempfront = "";
    
    for(int i = 0; i < phone_book.size(); i++){
        tempfront = phone_book[i];
        for(int j = 0; j < phone_book.size(); j++){
            if(i != j){
                if(phone_book[j].find(tempfront) == 0){
                    answer = false;
                    break;
                }
            }
        }
    }
    return answer;
}

왜 안 될까.. 하다가 if문을 한 줄로 만들고, 출력을 바로 return했더니 효율성 테스트에서 통과했다.

아래는 정답코드....

 

는 더 이상 정답이 아니게 됨..ㅠㅠ 3월 4일 이후로 효율성 테스트 2문제가 추가된 듯 하다.

 

테케가 변경되면 문제 푼 사람들에 한 해서 이메일이나 알림이 왔음 좋겠다.

 

 

 

 

이전에 정답이었던 내 코드가.. 더 이상 테케를 통과하지 않는 코드가 되었다.

그래서 다른 사람의 풀이를 참고하여 정답 코드로 올린다.

 

🌱 정답코드

풀이방법 1

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

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

    sort(phoneBook.begin(), phoneBook.end()); // 사전 순 정렬

    for ( int i = 0 ; i < phoneBook.size() - 1 ; i++ )
    {
        if ( phoneBook[i] == phoneBook[i+1].substr(0, phoneBook[i].size()) )
        {
            answer = false;
            break;
        }
    }

    return answer;
}

// 출처 : https://programmers.co.kr/learn/courses/30/lessons/42577/solution_groups?language=cpp

 

풀이방법 2

#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

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

    unordered_map<string, int> hash_map;
    for(int i = 0; i < phone_book.size(); i++)
        hash_map[phone_book[i]] = 1;
        //map.insert({phone_book[i], 1}); 도 가능

    for(int i = 0; i < phone_book.size(); i++) {
        string phone_number = "";
        for(int j = 0; j < phone_book[i].size(); j++) {
            phone_number += phone_book[i][j];
            if(hash_map[phone_number] && phone_number != phone_book[i])
                answer = false;
        }
    }

    return answer;
}

// 출처 : https://programmers.co.kr/learn/courses/30/lessons/42577/solution_groups?language=cpp

 

cout  <<  phone_book[ i ]  -->> 119 cout <<  phone_book[ i ][ j ]  <<  '  ' <<  phone_number  <<  endl -->> 1   1          1   11          9   119

→

 

 

 

++) 추가.

이 문제유형은 해시였구나...

풀이 방식은 여기

 

나는 언제 문제만 보고, 아 이건 00유형이구나! 라고 생각할까...

아직 갈 길이 머네...ㅠㅠㅠ.. 내일 아침에 일어나서 hash로 다시 참고해봐야겠다.

#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

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

    unordered_map<string, int> hash_map;
    for(int i = 0; i < phone_book.size(); i++)
        hash_map[phone_book[i]] = 1;

    for(int i = 0; i < phone_book.size(); i++) {
        string phone_number = "";
        for(int j = 0; j < phone_book[i].size(); j++) {
            phone_number += phone_book[i][j];
            if(hash_map[phone_number] && phone_number != phone_book[i])
                answer = false;
        }
    }

    return answer;
}

 

 

 

Level 2 skill check

아놔..;

Level 2 skill check에서 다시 만났는데,

효율성 테스트 3, 4 통과 못 했다..ㅎ

(+ 이전에는 통과했는데 3/4일에 테케가 추가되었다고 한당.)

아마 해시로 안 풀어서 그런 것 같다... for문을 두 번 썼으니 머.. 말 다 했징...

 

다른 사람의 풀이 1 )

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

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

    sort(phoneBook.begin(), phoneBook.end()); // 사전 순 정렬

    for ( int i = 0 ; i < phoneBook.size() - 1 ; i++ )
    {
        if ( phoneBook[i] == phoneBook[i+1].substr(0, phoneBook[i].size()) )
        {
            answer = false;
            break;
        }
    }

    return answer;
}

// 출처 : https://programmers.co.kr/learn/courses/30/lessons/42577/solution_groups?language=cpp

 

그런데 다른 사용자들은 substr 보다 find가 이론적으론 빠르다고 하네요 라고 한다.

 

암튼 두 개의 풀이 모두 최근 변경된 테케도 통과한다.

 

 

다른 사람의 풀이 2 )

#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

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

    unordered_map<string, int> hash_map;
    for(int i = 0; i < phone_book.size(); i++)
        hash_map[phone_book[i]] = 1;

    for(int i = 0; i < phone_book.size(); i++) {
        string phone_number = "";
        for(int j = 0; j < phone_book[i].size(); j++) {
            phone_number += phone_book[i][j];
            if(hash_map[phone_number] && phone_number != phone_book[i])
                answer = false;
        }
    }

    return answer;
}

// 출처 : https://programmers.co.kr/learn/courses/30/lessons/42577/solution_groups?language=cpp