✍️문제 설명
전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.
- 구조대 : 119
- 박준영 : 97 674 223
- 지영석 : 11 9552 4421
전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.
제한 사항- phone_book의 길이는 1 이상 1,000,000 이하입니다.
- 각 전화번호의 길이는 1 이상 20 이하입니다.
- 같은 전화번호가 중복해서 들어있지 않습니다.
조건으로 얻을 수 있는 정보
1. 배열의 길이가 `10^6` 이므로, 시간복잡도 `O(n x logn)`이 되도록 구현하여야 1초(10^8) 내에 실행 가능
2. `O(n^2)` 방법은 시간 내에 처리 불가능하지만, 시간이 부족하면 이를 채택 (실전)
1️⃣ Brute False
누구나 가장 먼저 생각나는 방법으로, 각 phone_number를 순회하면서 해당 번호를 접두어로 사용하고 있는 phone_number가 있는지 판단하는 방법이다.
- 최소한의 최적화를 위해, 비교하는 두 phone_number를 문자열이 아닌 숫자로 변환하여 비교하였다.
is_jupdo : 문자열 비교
is_jupdo2 : 숫자 비
// #시도1. Brute false 문자열 비교, 시간초과
function is_jupdo(target, diff) {
const target_len = target.length;
for (let i = 0; i < target_len; i++) {
if (target[i] !== diff[i]) {
return false;
}
}
return true;
}
// #시도2. Brute False 숫자 비교, 시간초과
function is_jupdo2(target, diff, power_10) {
const target_len = target.length;
const diff_len = diff.length;
if (Math.floor(diff / power_10[diff_len - target_len]) - target === 0) {
return true;
}
return false;
}
function solution(phone_book) {
const len = phone_book.length;
const power_10 = [1];
// 10의 거듭제곱 값 넣기
for (let i = 1; i <= 20; i++) {
power_10[i] = power_10[i - 1] * 10;
}
phone_book.sort((a, b) => a.length - b.length);
for (let i = 0; i < len - 1; i++) {
const target = phone_book[i];
for (let j = i + 1; j < len; j++) {
const diff = phone_book[j];
// Compare
if (is_jupdo2(target, diff, power_10)) {
return false;
}
}
}
return true;
}
2️⃣Hash Table
1. phone_number 값을 객체 (Hash Table)에 저장한다. (아래 그림 참고)
2. 각 phone_number를 순회하며, 생성가능한 모든 접두어가 객체(Hash Table)에 존재하는지 확인한다.
// 시도3: Hash Table만들기
function solution(phone_book) {
const table = {};
for (const phone of phone_book) {
table[phone] = true;
}
for (const phone of phone_book) {
const len = phone.length;
for (let i = 1; i < len; i++) {
const substr = phone.substring(0, i);
if (table[substr] === true) {
return false;
}
}
}
return true;
}
분석
1️⃣Brute False
- solution 함수에서는 전화번호를 길이 순으로 정렬한 후, 각 번호와 그 다음 번호들 간의 비교를 반복한다.
- 여기서 이중 반복문을 사용하므로, 시간 복잡도는 최악의 경우 O(n^2)이다.
- 또한, is_jupdo 호출은 두 문자열의 길이에 비례하여 O(m) 시간이 소요되며, 이는 두 문자열 길이의 최대값에 의해 결정된다.
- 따라서 전체 시간 복잡도는 `O(n^2×m)`로, 전화번호의 수가 많거나 각 번호의 길이가 길면 성능이 최악이다.
2️⃣Hash Table
- 해시 테이블에 각 전화번호를 저장한 후, 각 전화번호의 접두사가 테이블에 있는지 확인한다. (O(n))
- 각 phone_number의 길이-1 만큼 hash table에 접두어가 있는지 확인한다. (O(m))
- 따라서, 이 방법의 시간 복잡도는 `O(n×m)`로, n은 전화번호 개수이고, m은 각 전화번호의 길이이다.
'PS' 카테고리의 다른 글
| [파이썬] 코테 꿀팁 (2) | 2024.10.10 |
|---|---|
| Javascript PS 꿀팁 저장소 (0) | 2024.06.29 |
