◼️ 문제
1. 문제 설명
2. 제한사항
3. 입출력
◼️ 풀이
✏️ 전반적인 풀이과정
- phone_book 배열(전화번호 목록)을 정렬한다.
- 정렬된 배열에서 이웃된 요소끼리만 확인하여 접두사 번호가 있는지 찾는다.
2-1. 배열 순회 중 접두사 번호를 찾으면 바로 false를 반환한다. - 끝까지 찾지 못했다면 true를 반영한다.
📃 풀이과정 추가 설명
문자열 정렬
sort의 기본 정렬 방식은 유니코드의 순서에 따른다.
이런 점 때문에, 숫자 배열은 문자로 바꿔서 정렬하는 방식을 채택한다고 한다.
숫자 배열인 [1, 10, 2]를 정렬하면 [1, 10, 2] 이렇게 정렬이 되는 것이다.
평소라면 이런 정렬 방식은 우리가 원하는 방식이 아니기 때문에 sort 메서드에 정렬 방식을 따로 입력할 것이다.
그런데 이 문제만큼이 이 정렬 방식이 찰떡이다.
앞부분부터 동일한 숫자 구성으로 정렬해주기 때문이다.
이렇게 정렬하면 접두사 번호를 찾는 과정도 이중 for문을 돈다거나, 객체를 이용할 필요가 없다.
그냥 앞뒤 요소만 비교하면 되는것이다.
기본 정렬 방식이 도움이 되는 문제는 처음봐서 새로운 경험이었다.
startsWith
문자 내장 객체의 메서드 중 하나이다.
특정 문자로 시작하는지 여부를 반환하는 함수로, 코테 문제를 풀면서 오늘 처음 적용해봤다.
이렇게 내장 객체 메서드를 많이 알고 적절한 상황에 적용하면
머리가 덜 고생한다^_^
😓 헤맸던 이유
100만개의 배열을 정렬한다?
처음에는 100만개의 배열을 정렬한다는 것 자체가 시간 초과가 발생할 것이라 생각했다.
그래서 애초에 정렬 아이디어를 배제하고 생각했다.
그러나 도저히 풀어낼 방법을 모르겠어서 에라 모르겠다 싶어 적용했는데 해결이 되었다..!
왜 해결이 되었을까 싶어 일단 자바스크립트의 sort 메서드의 시간 복잡도를 알아보았다.
자바스크립트의 sort 메서드는 O(nlogn) 시간복잡도를 가진다고 한다.
문제에서는 최대 100만개였으니 계산해보면 약 2천만 정도라고 한다.
나는 3천만 이내로 푸는 것을 목표로 하고 있었는데... 범위 이내에 드는 연산 횟수였다.
띠로리... 덕분에 sort 시간복잡도도 배웠고 좋았다🥹
💻 코드
function solution(phone_book) {
phone_book.sort();
for (let i = 0; i < phone_book.length - 1; i++) {
if (phone_book[i + 1].startsWith(phone_book[i])) return false;
}
return true;
}◼️ 틀렸던 풀이
몇몇 실행 케이스가 실패되었고, 시간 초과도 발생한 풀이이다.
전체적인 로직은 각 전화번호 길이 별로 배열로 관리하고, 배열들은 객체로 관리하고자 했던 방법이다.
배열을 객체로 관리하고 있다고 해도 결국엔 배열을 돌아야 하고
최악의 경우 100만 가까이 길이의 배열을 돌아야 할 수도 있어서
이 풀이가 정답이 아니라는 건 너무나도 알았으나,
그래도 일단 건들려보면 더 좋은 생각이 나지 않을까 싶어 구현했다.
틀렸던 코드이지만 확실히 이전보다 배열이나 객체 내장 메서드를 잘 활용하고 있다는 점에서
나름대로 의의가 있었던 코드이다.
💻 코드
function solution(phone_book) {
const phoneNumber = {}
for(let i = 1; i < 20; i++) {
phoneNumber[i] = []
}
for(const phone of phone_book) {
for(let i = 1; i < phone.length; i++) {
if(phoneNumber[i].some((num) => phone.startsWith(num))) return false
}
if(phone.length < 20) phoneNumber[phone.length].push(phone)
}
return true
}