[프로그래머스] 전화번호 목록 (문제 설명, 해결 과정, 코드 전문, c++)

• 문제 설명
• 해결 과정
• 코드 전문

 

문제 설명

 

 

본 문제는 프로그래머스의 전화번호 목록 문제입니다.

 

출 처 : https://programmers.co.kr/learn/courses/30/lessons/42577#

 

 

 

 

해결 과정

 

 

배열이나 트라이 로도 충분히 해결할 수 있지만 속도성능면에서 조금 까다로운 문제라, 이번의 경우 해시로 해결하였습니다. 앞의 배열이나 트라이로도 충분히 시간 안에 해결이 가능합니다. 어떤 분은 사전순으로 문자열들을 정렬해서

인근 인덱스만 비교를 하였더군요.

저의 풀이의 경우 배열 안 모든 문자열들을 해시셋 안에 넣고 반복문을 통해 모든 문자열들의 자기 접두어를 포함한 모든 문자열들 뽑아 해시셋에 존재여부를 비교하여 모든 반복이 진행될 때 까지 일치함이 없을 때는 true 반환. 그렇지 않을 경우 false를 반환합니다.

 

 

 

 

코드 전문

 

 

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

using namespace std;

bool solution(vector<string> p) {
    bool answer = true;  
    unordered_set<string> h_s;
    for (auto s : p)
    {
        h_s.insert(s);
    }
    for (auto s : p)
    {
        for (int i=1; i<s.size(); i++)
        {
            if (h_s.find(s.substr(0,i)) != h_s.end()) {answer = false; break;}
        }
        if (answer == false) break;
    }
    
    return answer;
}

 

 

 

 

느낀 점 (잡설 99% , 배운점 1%(많은 편))

 

해시 특성 상 문자열 key보다 정수형 key의 비교가 더 빨라 그렇게 풀려했더니 문자열의 최대 길이가 20으로

정수형을 넘어서네요. vector<string>을 sort로 정렬하면 사전순으로 정렬이 되는군요.  substr의 경우

매개변수가 시작인덱스, 길이 라는 걸 다시 한 번 각인하였습니다. 그리고 find함수 최고

 

 

 

 

 

 

 

 

긴 글 읽어주셔서 감사합니다. 

부족한 점이 있다면 부디 알려주시면 감사하겠습니다.