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

본 블로그는 비상업적, 비영리적 용도의 학업만을 위해 글을 게시합니다.

1. 문제 분석

• 접두어가 같다는 것 = 정렬을 해서 순서대로 비교하면 되지 않을까 생각했다.
• 첫번째 숫자대로 분류를 하고 각 분류 내에서 완전 탐색을 해야할 것 같다.

2. 문제 풀이 과정(삽질)

• 처음에는 맨 앞숫자만으로 분류해 전체를 비교할 생각이었는데, 생각해보니 문자열을 정렬시키면 "0123456789" 순으로 정렬될 것이고, 첫번째나 두번째나 똑같다.
• 결국 바로 뒤에있는 문자열과만 비교하면 된다는걸 알았다.

3. 문제 해결

• 바로 위에 생각난 대로, 정렬 후 뒤에 원소와 비교해 나가면서 판단을 했다.

4. 코드

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

using namespace std;

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

5. 고수의 코드를 보고 배우기

• 나는 뒤에 문자열이 앞의 문자열보다 짧으면 안될거로 생각해서 조건을 넣었는데, 굳이 안해도 되나보다.

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;
}