프로그래머스 전화번호 목록

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

프로그래머스

이번에는 Level2 문제를 풀어보았다. 이번에도 해시 문제를 풀어보았다. 문제를 읽어보면 처음에는 단순하게 접근하면 쉬울거라고 생각했다. 음…처음에 보고 문자열 비교니깐 그냥 for문으로 반복시켜주면 될거라고 생각했다.

근데 당연히 시간초과가 뜨겠지ㅎㅎ라는 생각을 가지며 그냥 무작정 코드를 작성하였다.

내가 생각한 알고리즘은 단순했다. 다음과 같다.

 

1. 먼저 첫 번째 문자와 바로 다음 문자 길이를 비교해주는 반복문을 만들어주었다.
2. min()알고리즘을 이용해서 길이가 더 문자의 길이를 저장해준다.
3. 2번과 같이한 이유는 어차피 짧은 길이의 문자 만큼만 비교해주면 된다고 생각해서 이다.
4. 반복문을 통해서 문자를 하나씩 비교해주면서 문자가 다를 경우 selection 변수에 false값을 넣어주었다.
5. 마지막으로 select에 false값이 들어있으면 true를 출력, true값이 들어있으면 false를 출력하도록 조건문을 만들어줬다.

 

코드

#include <string>
#include <vector>
#include <iostream>
#include <unordered_set>

using namespace std;

bool solution(vector<string> phone_book) {
    bool answer = true;
    
    for(int i = 0; i < phone_book.size() - 1; i++) {
        for(int j = i + 1; j < phone_book.size(); j++) {
            int min_length = min(phone_book[i].length(), phone_book[j].length());
            
            bool select = true;
            
            for(int k = 0; k < min_length; k++) {
                if(phone_book[i][k] != phone_book[j][k]) {
                    select = false;
                    break;
                }
            }
            
            if(select)
                return false;
        }
    }
    
    return answer;
}

ㅋㅋㅋㅋㅋ될 뻔 했는데 역시나 시간초과가 떴다. 컴퓨터는 정확하다 봐주는게 없다

결국에는 해시를 이용해서 풀어야 된다는 의미 어떻게 서든지 시간을 줄여야 한다.

 

해시를 이용한 코드

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

using namespace std;

bool solution(vector<string> phone_book) {
    unordered_map<string, int> hash_map;

    // 해시맵에 전화번호 저장
    for (string number : phone_book) {
        hash_map[number] = 1;
    }

    // 각 전화번호의 접두어가 해시맵에 있는지 확인
    for (string number : phone_book) {
        string prefix = "";
        for (char digit : number) {
            prefix += digit;
            if (hash_map.find(prefix) != hash_map.end() && prefix != number) {
                // 현재 전화번호의 접두어가 다른 전화번호와 일치하면 false 반환
                return false;
            }
        }
    }

    return true;
}

해시를 사용한 알고리즘:

1. 전화번호부를 확인하며, 전화번호를 해시맵에 넣는다.
   • 해시맵은 전화번호를 빠르게 찾는 역할을 한다. 예를 들면, '119' 전화번호를 넣으면, '119'로 시작하는 번호를 쉽게 찾을 수 있다.
2. 전화번호부를 다시 둘러보며, 한 전화번호가 다른 전화번호의 시작부분인지 확인한다.
   • 각 전화번호로 가능한 모든 시작부분을 만들어서, 그게 다른 전화번호인지 확인해 본다.
   • 만약 전화번호의 시작부분이 다른 전화번호라면, 그건 문제가 생긴다는 것이다.
3. 전화번호의 시작부분이 다른 전화번호가 아니라면, 그건 문제가 없다는 것이다. 그럴 경우 함수는 '참(true)'을 알려준다.
   • 여기서 해시맵의 역할은 전화번호를 빠르게 찾아볼 수 있게 하는 거다. 예를 들어 '119'라는 전화번호를 해시맵에 저장하면, 나중에 '119'가 접두어로 있는지 쉽게 확인할 수 있다.

 

다른 사람의 풀이법

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

phoneBook[i+1].substr(0, phoneBook[i].size())는 현재 전화번호의 길이만큼 다음 전화번호를 잘라내어 비교한다. 여기서 substr() 함수는 문자열의 일부분을 추출하는 함수이다.

 

즉, 이 코드는 현재 전화번호가 다음 전화번호의 접두어인지를 비교한다. 만약 현재 전화번호가 다음 전화번호의 접두어라면, phoneBook[i] == phoneBook[i+1].substr(0, phoneBook[i].size())는 참(true)이 된다.

 

예를 들어, phoneBook[i]가 "119"이고, phoneBook[i+1]이 "1195524421"인 경우를 생각해보면 phoneBook[i+1].substr(0, phoneBook[i].size())는 "11955"가 된다. 즉, "1195524421"에서 "119"까지만 잘라내어 비교하게 된다.

 

따라서 이 조건문은 현재 전화번호가 다음 전화번호의 접두어인지 확인하여, 접두어인 경우에는 answer를 false로 설정한다. 이는 주어진 전화번호부에 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 반환한다는 것을 의미한다.

 

이렇게 쉽게 풀 수 있다는게 인상깊다…더 열심히 해야지