🔎 문제
🧩 구현과정 및 코드
개인 토글 영역에 구현 과정과 코드를 자유롭게 작성해주시면 됩니다.
사용할 데이터 구조와 풀이 방향성
적용할 알고리즘 혹은 메서드
수영
구현
- string.startsWith(search) 첫 문자열이 시작되는지 접근
- search도 포함되는 문제(비효율)
- 힌트:
array.sort()를 하면 사전식을 따른다.
코드
function solution(phone_book) { let array = [...phone_book]; array.sort(); for(let i = 0; i < array.length - 1; i++){ let isPrefix = array[i+1].startsWith(array[i]); if(isPrefix) return false; } return true; }
정은
구현
1) 정렬 ⇒ python의 sort() 사용
2) 뒤의 숫자가 앞의 숫자로 시작하는지 판단
코드
- 내가 최초로 푼 코드
def solution(phone_book): answer = True phone_book.sort() #1) 정렬 for i in range(1,len(phone_book)): if phone_book[i][:len(phone_book[i-1])] == phone_book[i-1]: #2) 뒤의 숫자가 앞의 숫자로 시작하는가 return False return answer
- 다른 사람 풀이 참고 후 코드
def solution(phone_book): #불필요한 answer 변수 제거 phone_book.sort() for phone1, phone2 in zip(phone_book,phone_book[1:]): #zip으로 배열 원소 두개를 Pair로 if phone2.startswith(phone1): # startswith로 로직을 내가 안짜도 됨 return False return True
종혁
구현
- phone_book의 원소들을 길이에 따라 오름차순으로 배열
- 이 과정이 없으면 객체에 순서대로 저장이 안됨
- 길이가 짧은 원소부터 obj 객체에 저장하면서, 해당 전화번호가 있다는걸 표시
- slice(0,1) ~ slice(0,length)의 값이 obj에 있으면 → 접두사가 있다는 뜻이므로 return false
코드
function solution(phone_book) { const obj = {} phone_book.sort((a,b) => a.length - b.length) for(let i=0;i<phone_book.length;i++){ for(let j=0;j<phone_book[i].length;j++){ obj[phone_book[i]] = 1 if(phone_book[i].slice(0,j) in obj){ return false } } } return true }
재웅
구현
- 정렬 후 2중 루프 탐색
→ forEach 메서드는 return을 반환하지 않음
function solution(phoneBook) { phoneBook.sort() // 첫 번째 원소부터 순차적으로 탐색하면서, 기준 원소의 길이만큼의 접두사를 비교 // -> 최악의 경우 n*n 복잡도 소요? phoneBook.forEach((num,index)=>{ // phoneBook에서 index 이후 요소의 접두사 중 num과 일치하는 게 있으면 false 반환 const numLength = num.length phoneBook.slice(index+1).forEach((el)=>{ console.log(num,el.slice(0,numLength)) if(num===el.slice(0,numLength)) return false }) }) return true }
- for문으로 변환
→ 효율성 3,4 시간 초과..
function solution(phoneBook) { const length = phoneBook.length phoneBook.sort() // 첫 번째 원소부터 순차적으로 탐색하면서, 기준 원소의 길이만큼의 접두사를 비교 // -> 최악의 경우 n*n 복잡도 소요? for(let i=0; i<length; i++){ const target = phoneBook[i] const targetLength = phoneBook[i].length for(let j=i+1; j<length; j++){ if(target === phoneBook[j].slice(0,targetLength)) return false } } return true }
- 다르게 접근
→ includes 메서드도 O(n) 복잡도를 갖기 때문에, 결과적으로 똑같은 연산량을 가짐
→ O(1) 복잡도로 포함여부를 확인할 수 있는 해시로 구현
function solution(phoneBook) { for (const number of phoneBook) { for (let i = 1; i < number.length; i += 1) { const prefix = number.slice(0, i); if (phoneBook.includes(prefix)) return false; }; }; return true }
- 해시 맵
function solution(phoneBook) { const map = new Map() for (const number of phoneBook) { map.set(number,true) }; for (const number of phoneBook) { for (let i = 1; i < number.length; i += 1) { const prefix = number.slice(0, i); if (map.has(prefix)) return false; }; }; return true }
✏️ 후기
문제를 풀고 느낀 점, 막혔던 부분 혹은 개선 사항 등을 자유롭게 작성해주시면 됩니다.
수영
- 정렬의 중요성..
- array.sort()는 사전식을 따른다! ["1", "2", "3", "100"] → array.sort() → ["1", "100", "2", "3"]
정은
- (다른 풀이) zip, startswith 같이 파이썬 문법을 사용하면 더 간결하게 사용할 수 있을 것 같다.
다시 풀어보기
- 생각해보니 이 문제는 한번이라도 매칭되는지 여부를 판단하는 문제라 앞, 뒤만 비교해도 됐었는데,
만약 매칭되는 전체 개수를 구하는 문제라면 이 방법은 맞지 않다.
- 취지에 맞게 해쉬를 사용하지는 않았다,,ㅎ
- 소요시간 : 5분
종혁
- 원소가 중복해서 존재하지 않기 때문에, 길이가 같은 원소들은 절대 서로의 접두사가 될 수 없음
- 길이가 짧은 원소가 → 길이가 긴 원소의 접두사가 됨
재웅
- 탐색에는 해시가 최고..