Younho9 NotesProgrammers 42577. 전화번호 목록
Title
Programmers 42577. 전화번호 목록
Category
AlgorithmTags
Aliases
Programmers 42577. 전화번호 목록Created
3 years ago
Updated
last year
| 문제 유형 | 난이도 | 걸린 시간 | 해결 유무(✅/❌) |
|---|---|---|---|
| 해시 | lv.1 | 30분 | ✅ |
설계 방법
해시로 풀이하는 법이 떠오르지 않았음.
phone_book을 먼저 정렬함.['119', '97674223', '1195524421'] -> ['119', '1195524421', '97674223']로정렬됨.
sort된 배열을reduce로 순회하며 현재 값이 그 이전 값으로startsWith하는지 판단함.startsWith이true라면answer를false로 바꾸고reduce를early break함.
코드
JavaScript
javascript
function solution(phone_book) {
let answer = true;
phone_book
.sort()
.slice(0)
.reduce((short, long, _, arr) => {
if (long.startsWith(short)) {
answer = false;
arr.splice(1);
}
return long;
});
return answer;
}
function solution(phone_book) {
let answer = true;
phone_book
.sort()
.slice(0)
.reduce((short, long, _, arr) => {
if (long.startsWith(short)) {
answer = false;
arr.splice(1);
}
return long;
});
return answer;
}
Python
python
def solution(phone_book):
phone_book = sorted(phone_book)
for short, long in zip(phone_book, phone_book[1:]):
if long.startswith(short):
return False
return True
def solution(phone_book):
phone_book = sorted(phone_book)
for short, long in zip(phone_book, phone_book[1:]):
if long.startswith(short):
return False
return True
시간 복잡도
sort() : O(NlogN) reduce : O(N)
O(NlogN) + O(N) 맞나..?
어려웠던 점
해시로 분류되어 있어서 생각이 해시로 고정되었는데, 해시로 푸는 방법이 쉽게 안떠올랐음.
프로그래머스에서 JS를 지원하지 않는 문제라, 파이썬으로 먼저 풀었어야 했음.