💻 전화번호 목록
분류 : Hash (해시)
사용 언어 : C++
🤔 문제 이해
문제 설명
전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.
- 구조대 : 119
- 박준영 : 97 674 223
- 지영석 : 11 9552 4421
전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.
제한 사항
-
phone_book의 길이는 1 이상 1,000,000 이하입니다.
- 각 전화번호의 길이는 1 이상 20 이하입니다.
- 같은 전화번호가 중복해서 들어있지 않습니다.
해결 방안
여러 번호들 중에 한 번호가 다른 번호의 접두어 인 경우를 확인해야 한다.
방법은 여러가지 일 것이다.
이중 for문을 사용하여 모든 경우의 수를 돌려도 되고, vector 를 정렬하고 순차적으로 대조해봐도 되고, STL의 map이나 set을 사용해도 될 것이다.
💡 문제 풀이
방법 1 )
모든 경로를 돌아 접두어인지 체크한다.
#include <string>
#include <vector>
using namespace std;
bool solution(vector<string> phone_book) {
for (int i = 0; i < phone_book.size(); i++) {
for (int j = 0; j < phone_book.size(); j++) {
// 이중 for문
// 다른 전화번호를 선택된 전화번호의 크기만큼 잘라서 비교
if (phone_book[i] == phone_book[j].substr(0, phone_book[i].length()) && i != j) {
return false;
}
}
}
return true;
}
/*
정확성 테스트
테스트 1 〉 통과 (0.01ms, 3.96MB)
테스트 2 〉 통과 (0.01ms, 3.97MB)
테스트 3 〉 통과 (0.01ms, 3.96MB)
테스트 4 〉 통과 (0.01ms, 3.95MB)
테스트 5 〉 통과 (0.01ms, 3.98MB)
테스트 6 〉 통과 (0.01ms, 3.9MB)
테스트 7 〉 통과 (0.01ms, 3.79MB)
테스트 8 〉 통과 (0.01ms, 3.91MB)
테스트 9 〉 통과 (0.01ms, 3.96MB)
테스트 10 〉 통과 (0.01ms, 3.95MB)
테스트 11 〉 통과 (0.01ms, 3.95MB)
테스트 12 〉 통과 (0.01ms, 3.93MB)
테스트 13 〉 통과 (0.01ms, 3.98MB)
테스트 14 〉 통과 (15.74ms, 3.94MB)
테스트 15 〉 통과 (14.64ms, 3.94MB)
테스트 16 〉 통과 (108.23ms, 3.92MB)
테스트 17 〉 통과 (155.95ms, 3.96MB)
테스트 18 〉 통과 (214.11ms, 3.97MB)
테스트 19 〉 통과 (247.25ms, 3.92MB)
테스트 20 〉 통과 (129.87ms, 3.95MB)
효율성 테스트
테스트 1 〉 통과 (0.68ms, 4.54MB)
테스트 2 〉 통과 (0.64ms, 4.5MB)
테스트 3 〉 실패 (시간 초과)
테스트 4 〉 실패 (시간 초과)
채점 결과
정확성: 83.3
효율성: 8.3
합계: 91.7 / 100.0
*/시간 복잡도 : n^2
이중 for문을 통하여 모든 경우의 수를 돌려 보았다.
데이터량이 많아지자 속도는 기하급수적으로 커졌다.
방법 2 )
변수를 정렬하고, 바로 앞의 변수랑 대조해본다.
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
bool solution(vector<string> phone_book) {
// algorithm의 sort를 통하여 정렬
sort(phone_book.begin(), phone_book.end());
for (int i = 1; i < phone_book.size(); i++) {
// 현 전화번호를 앞의 전화번호의 길이만큼 잘라서 비교
if (phone_book[i - 1] == phone_book[i].substr(0, phone_book[i - 1].length())) return false;
}
return true;
}
/*
정확성 테스트
테스트 1 〉 통과 (0.01ms, 3.96MB)
테스트 2 〉 통과 (0.01ms, 3.97MB)
테스트 3 〉 통과 (0.01ms, 3.93MB)
테스트 4 〉 통과 (0.01ms, 3.92MB)
테스트 5 〉 통과 (0.01ms, 3.95MB)
테스트 6 〉 통과 (0.01ms, 3.97MB)
테스트 7 〉 통과 (0.01ms, 3.97MB)
테스트 8 〉 통과 (0.01ms, 3.94MB)
테스트 9 〉 통과 (0.01ms, 3.95MB)
테스트 10 〉 통과 (0.01ms, 3.93MB)
테스트 11 〉 통과 (0.01ms, 3.94MB)
테스트 12 〉 통과 (0.01ms, 3.91MB)
테스트 13 〉 통과 (0.01ms, 3.97MB)
테스트 14 〉 통과 (0.31ms, 3.97MB)
테스트 15 〉 통과 (0.38ms, 3.93MB)
테스트 16 〉 통과 (0.52ms, 3.97MB)
테스트 17 〉 통과 (0.62ms, 4.06MB)
테스트 18 〉 통과 (0.90ms, 3.95MB)
테스트 19 〉 통과 (0.95ms, 3.93MB)
테스트 20 〉 통과 (0.92ms, 3.93MB)
효율성 테스트
테스트 1 〉 통과 (3.77ms, 4.25MB)
테스트 2 〉 통과 (3.75ms, 4.27MB)
테스트 3 〉 통과 (86.55ms, 35.6MB)
테스트 4 〉 통과 (83.58ms, 31.4MB)
채점 결과
정확성: 83.3
효율성: 16.7
합계: 100.0 / 100.0
*/시간 복잡도 : n * log n + (n-1)
algorithm의 sort 를 통하여 순차 정렬을 해주면 숫자가 더 빠르고 짧은 순으로 정렬될 것이다.
(숫자가 길더라도 앞 번호가 빠르면 앞에 위치한다.)
이를 통하여 바로 앞의 번호와 대조하여 조건의 맞는 번호가 있는지 찾았다.
방법 3 )
Unordered_set을 사용하여 find한다.
#include <string>
#include <vector>
#include <unordered_set>
using namespace std;
bool solution(vector<string> phone_book) {
unordered_set<string> phone_book_set(phone_book.begin(), phone_book.end());
for (int i = 0; i < phone_book.size(); i++) {
string text = "";
for (int j = 0; j < phone_book[i].length(); j++) {
text += phone_book[i][j];
if (phone_book_set.find(text) != phone_book_set.end() && text != phone_book[i]) return false;
}
}
return true;
}
/*
정확성 테스트
테스트 1 〉 통과 (0.02ms, 3.89MB)
테스트 2 〉 통과 (0.02ms, 3.89MB)
테스트 3 〉 통과 (0.01ms, 3.88MB)
테스트 4 〉 통과 (0.01ms, 3.89MB)
테스트 5 〉 통과 (0.02ms, 3.97MB)
테스트 6 〉 통과 (0.02ms, 3.88MB)
테스트 7 〉 통과 (0.01ms, 3.95MB)
테스트 8 〉 통과 (0.02ms, 3.94MB)
테스트 9 〉 통과 (0.01ms, 3.97MB)
테스트 10 〉 통과 (0.01ms, 3.98MB)
테스트 11 〉 통과 (0.04ms, 3.71MB)
테스트 12 〉 통과 (0.02ms, 3.93MB)
테스트 13 〉 통과 (0.03ms, 3.91MB)
테스트 14 〉 통과 (0.63ms, 3.96MB)
테스트 15 〉 통과 (1.33ms, 3.92MB)
테스트 16 〉 통과 (1.98ms, 4.07MB)
테스트 17 〉 통과 (2.44ms, 4.18MB)
테스트 18 〉 통과 (2.92ms, 3.97MB)
테스트 19 〉 통과 (1.69ms, 3.96MB)
테스트 20 〉 통과 (3.35ms, 3.92MB)
효율성 테스트
테스트 1 〉 통과 (3.24ms, 5.21MB)
테스트 2 〉 통과 (3.55ms, 5.21MB)
테스트 3 〉 통과 (294.60ms, 55.3MB)
테스트 4 〉 통과 (269.55ms, 48.5MB)
채점 결과
정확성: 83.3
효율성: 16.7
합계: 100.0 / 100.0
*/시간 복잡도 : text_length n log n
set의 find는 log n 정도의 시간 복잡도를 갖고 있어 많은 양의 데이터에서 무엇을 찾는데 용이하다.
unordered_multiset을 이용한 이유는 문제 속에 동명이인이 있을 수 있어 multiset을 사용하고, 자체적으로 정렬을 하지 않기 때문에 multiset보다 빠르다.
방법 4 )
unordered_map을 사용하여 비교한다.
#include <string>
#include <vector>
#include <unordered_map>
using namespace std;
bool solution(vector<string> phone_book) {
unordered_map<string, bool> phone_book_map;
for (const auto& phone_number : phone_book) {
phone_book_map.insert({ phone_number, true });
}
for (int i = 0; i < phone_book.size(); i++) {
string text = "";
for (int j = 0; j < phone_book[i].length(); j++) {
text += phone_book[i][j];
if (phone_book_map[text] && text != phone_book[i]) return false;
}
}
return true;
}
/*
정확성 테스트
테스트 1 〉 통과 (0.01ms, 3.96MB)
테스트 2 〉 통과 (0.01ms, 3.98MB)
테스트 3 〉 통과 (0.01ms, 3.73MB)
테스트 4 〉 통과 (0.01ms, 3.97MB)
테스트 5 〉 통과 (0.01ms, 3.85MB)
테스트 6 〉 통과 (0.02ms, 3.99MB)
테스트 7 〉 통과 (0.01ms, 3.97MB)
테스트 8 〉 통과 (0.01ms, 3.97MB)
테스트 9 〉 통과 (0.01ms, 3.96MB)
테스트 10 〉 통과 (0.01ms, 3.85MB)
테스트 11 〉 통과 (0.01ms, 3.95MB)
테스트 12 〉 통과 (0.01ms, 3.96MB)
테스트 13 〉 통과 (0.01ms, 3.91MB)
테스트 14 〉 통과 (1.70ms, 3.97MB)
테스트 15 〉 통과 (1.86ms, 4.01MB)
테스트 16 〉 통과 (5.73ms, 5.52MB)
테스트 17 〉 통과 (7.82ms, 6.32MB)
테스트 18 〉 통과 (9.35ms, 6.51MB)
테스트 19 〉 통과 (4.47ms, 5.02MB)
테스트 20 〉 통과 (5.57ms, 5.27MB)
효율성 테스트
테스트 1 〉 통과 (2.62ms, 5.34MB)
테스트 2 〉 통과 (2.64ms, 5.17MB)
테스트 3 〉 통과 (271.88ms, 57.7MB)
테스트 4 〉 통과 (570.48ms, 114MB)
채점 결과
정확성: 83.3
효율성: 16.7
합계: 100.0 / 100.0
*/시간 복잡도 : n log n + text_length n
방법 3의 map 버전.
find 대신 [] 을 사용하면 더 빠르지 않을까 싶어서 만들어봤는데 결과는 아니었다.
(ง ᐖ)ว