[프로그래머스 > 고득점kit 해시] 전화번호 목록 (C++)

programmers.co.kr/learn/courses/30/lessons/42577

 

 

 

해시 kit의 두 번째 문제이다.

 

해시로 풀고 싶은데 계속 vector를 sort해서 풀게 된다..

 

아무튼 아이디어는 이렇다.

 

 

 

 

먼저 phone_book vector를 sort함수로 정렬한다. 

그럼 가장 길이가 짧고 알파벳 순서가 빠른 문자열들이 벡터의 앞 쪽에 위치한다.

 

이렇게 되면 인덱스 번호가 작은 벡터 값은 자신보다 인덱스 번호가 큰 벡터 값의 접두어가 될 가능성이 크다.

그러나 인덱스 번호가 큰 벡터 값이 자신보다 인덱스 번호가 작은 벡터 값의 접두어가 될 일은 절대 절대 없다.

 

그럼 이중 for문을 만들 수 있게 되는데,

접두어 후보를 head_number라고 칭하고, 접두어가 포함될 가능성이 있는 문자열을 compared_number라고 칭하자.

 

head_number는 자신 보다 뒤에 위치하는 벡터 값들과 하나씩 비교하면서 접두어 인지 아닌지

체크해주면 된다.

 

 

 

알고리즘을 도식화 하면 아래와 같다.

 

정렬된 vector의 접두어를 찾아나가는 알고리즘

 

 

 

코드로 한 번 살펴보자.

 

 

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

using namespace std;

bool solution(vector<string> phone_book) {
    bool answer = true;
    
    sort(phone_book.begin(), phone_book.end());
    
    int size = phone_book.size();
    
    for(int i=0; i<size-1; i++)
    {
        string head_number = phone_book[i];
        int head_number_length = phone_book[i].length();
        
        for(int j=i+1; j<size; j++)
        {
            string compared_number = phone_book[j];
            int cnt=0;
            for(int k=0; k<head_number_length; k++)
            {
                if(head_number[k]!=compared_number[k])
                {
                    break;
                }
                else
                {
                    cnt++;
                }
            }
            if(cnt==head_number_length)
            {
                return false;
            }
            
        }
    }
    
    
    return answer;
}

 

 

 

 

다른 사람들이 푼 정답 코드를 보니 같은 알고리즘인데도 substr등의 함수를 써서 훨씬 간단하게 줄였다.

잘 참고해서 좀 더 효율적인 코드를 짤 수 있게끔 계속 고민하자!

 

 

 

 

 

 

 

 

아무튼 제출 결과  정답!