[프로그래머스] Lv.2 전화번호 목록 c++

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

프로그래머스

 

전화번호부에 저장된 전화번호 중, 한 번호가 다른 번호의 접두어로 포함되어 있는지를 확인하는 문제입니다.

예를 들어, 전화번호 목록 ["119", "97674223", "1195524421"]에서 119는 1195524421의 접두어이므로 false입니다.

반면, 접두어 관계가 없는 목록 ["123", "456", "789"]에서는 결과가 true가 됩니다.

 

풀이 방법

알고리즘 고득점 Kit Hash에 있는 문제라 Hash 자료구조를 사용할까 고민했는데, 정렬을 활용하면 훨씬 쉽게 풀 수 있습니다.

예를 들어, ["567", "123", "88", "1235", "12"]라는 전화번호 목록이 있을 때,

sort를 사용하면 ["12", "123", "1235", "567", "88"]처럼 정렬됩니다.

이렇게 하면 접두어 관계가 있는 번호들이 자연스럽게 순서대로 정렬되어, 인접한 번호만 비교하면 쉽게 접두어 여부를 확인 가능합니다.

 

저는 for문을 전화번호부 크기 - 1만큼 돌리면서  string tmp 변수에 i+1번째 문자열을 0부터 현재 문자열의 길이만큼 자른 후 비교하는 방식으로 해결했습니다. 이렇게 하면 최소한의 비교로도 정답을 빠르게 구할 수 있습니다.

 

풀이 코드

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

using namespace std;

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