[코딩테스트] [프로그래머스] 전화번호 목록

문제

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

---

풀이

1. 원소 탐색 시 O(1)의 시간이 걸리는 unordered_set을 사용한다. phone_number의 값을 모두 set에 넣어준다.

2. phone_number vector를 순회하며 substr 함수로 부분문자열을 추출한다.
   2-1. 부분 문자열을 set에서 찾았다면 접두어 문자열이 존재한다는 뜻이기에 false를 반환한다.

---

코드

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

using namespace std;

bool solution(vector<string> phone_book) 
{  
    unordered_set<string> numbers(phone_book.begin(), phone_book.end());
    
    for (string number : phone_book)
    {
        for (int i = 1; i < number.size(); i++)
        {
            string subNumber = number.substr(0, i);
            
            if (numbers.find(subNumber) != numbers.end())
            {
                return false;
            }
        }
    }
    
    return true;
}

---

다른 풀이와 코드

0. 해시를 사용하지 않고, 정렬만으로 풀이한 다른 사람의 풀이이다.

1. algorithm 헤더의 sort 함수로 phone_book 벡터를 정렬한다.

2. phone_book 벡터를 순회하며 다음 원소의 부분 문자열과 현재 원소가 같다면 false를 반환한다.

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

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