📞

전화번호 목록

레벨

LV.2

날짜

Sep 22, 2023

링크

https://school.programmers.co.kr/learn/courses/30/lessons/42577

🔎 문제

school.programmers.co.kr

https://school.programmers.co.kr/learn/courses/30/lessons/42577

🧩 구현과정 및 코드

개인 토글 영역에 구현 과정과 코드를 자유롭게 작성해주시면 됩니다.

사용할 데이터 구조와 풀이 방향성

적용할 알고리즘 혹은 메서드

수영

구현

string.startsWith(search) 첫 문자열이 시작되는지 접근

search도 포함되는 문제(비효율)

힌트: array.sort()를 하면 사전식을 따른다.

코드

정은

구현

1) 정렬 ⇒ python의 sort() 사용

2) 뒤의 숫자가 앞의 숫자로 시작하는지 판단

코드

내가 최초로 푼 코드

다른 사람 풀이 참고 후 코드

종혁

구현

phone_book의 원소들을 길이에 따라 오름차순으로 배열

이 과정이 없으면 객체에 순서대로 저장이 안됨

길이가 짧은 원소부터 obj 객체에 저장하면서, 해당 전화번호가 있다는걸 표시

slice(0,1) ~ slice(0,length)의 값이 obj에 있으면 → 접두사가 있다는 뜻이므로 return false

코드

재웅

구현

정렬 후 2중 루프 탐색

→ forEach 메서드는 return을 반환하지 않음

for문으로 변환

→ 효율성 3,4 시간 초과..

다르게 접근

→ includes 메서드도 O(n) 복잡도를 갖기 때문에, 결과적으로 똑같은 연산량을 가짐

→ O(1) 복잡도로 포함여부를 확인할 수 있는 해시로 구현

해시 맵

✏️ 후기

문제를 풀고 느낀 점, 막혔던 부분 혹은 개선 사항 등을 자유롭게 작성해주시면 됩니다.

👧🏻

수영

정렬의 중요성..

array.sort()는 사전식을 따른다! ["1", "2", "3", "100"] → array.sort() → ["1", "100", "2", "3"]

👧🏻

정은

(다른 풀이) zip, startswith 같이 파이썬 문법을 사용하면 더 간결하게 사용할 수 있을 것 같다.

다시 풀어보기

생각해보니 이 문제는 한번이라도 매칭되는지 여부를 판단하는 문제라 앞, 뒤만 비교해도 됐었는데,

만약 매칭되는 전체 개수를 구하는 문제라면 이 방법은 맞지 않다.

취지에 맞게 해쉬를 사용하지는 않았다,,ㅎ

소요시간 : 5분

👦

종혁

원소가 중복해서 존재하지 않기 때문에, 길이가 같은 원소들은 절대 서로의 접두사가 될 수 없음

길이가 짧은 원소가 → 길이가 긴 원소의 접두사가 됨

👦🏻

재웅

탐색에는 해시가 최고..


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;
}


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


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
}


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
}


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
}


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
}