[코테] 99클럽 코테 스터디 1일차 TIL - 해시

항해 99클럽 코테 스터디는 앞으로 6주동안 이어질 예정.! 이참에 가능한 한에서 매일 미들러 문제를 풀어보면 좋을 것 같다.

 

Question1 - [미들러] 전화번호 목록 

 

문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/42577
전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

• 구조대 : 119
• 박준영 : 97 674 223
• 지영석 : 11 9552 4421

전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요

제한사항

• phone_book의 길이는 1 이상 1,000,000 이하입니다.
• 각 전화번호의 길이는 1 이상 20 이하입니다.

입출력 예

phone_bookreturn

["119", "97674223", "1195524421"]	false
["123", "456", "789"]	true
["12", "123", "1235", "567", "88"]	false

입출력 예 설명
예제 #2
한 번호가 다른 번호의 접두사인 경우가 없으므로, 답은 true입니다.
예제 #3
첫 번째 전화번호, “12”가 두 번째 전화번호 “123”의 접두사입니다. 따라서 답은 false입니다.

---

문제풀이 

 

trial1 

처음에 풀었던 방식은 정확도는 맞았지만 너무 비효율적이었음. 반복문을 두번 돌아서 시간 초과

key만 사용할거면 굳이 해시에 담는 과정도 필요가 없었다. 

def solution(phone_book):
    phone_hash = {}
    for idx, i in enumerate(phone_book) : 
        phone_hash[i] = idx
    
    for i in phone_hash : 
        for j in phone_hash : 
            if i!=j and i.startswith(j) :
                return False
    return True

 

trial2 

더 효율적이기 위해서 생각할 수 있는 방법은 전화번호부를 순서대로 우선 정렬하는 것.

정렬한 뒤에는 짧은 숫자부터 긴숫자까지 중복되는 숫자들이 이미 모여있을 것이므로, 유사한 번호들 중 가장 먼저 등장하는 접두어를 찾아서 비교하면 된다.

게다가 접두어가 있는 경우 바로 False를 반환해야 하므로, 가장 효율적이기 위해서는 바로 옆에 있는 숫자와 겹치는지만 비교하면 된다.

그 결과 효율성까지 통과했다.

그러나 이 풀이는 실상 정렬로 푼거라 해시를 사용하지 않았다는 단점이 있다. 

def solution(phone_book):
    phone_book.sort()
    
    for i in range(len(phone_book)-1):
        if phone_book[i+1].startswith(phone_book[i]):
            return False
    return True

 

trial3 ★

효율적으로 풀면서도 해시를 사용하는 방법이 없을까?  

앞선 풀이들에서는 접두사를 먼저 규정하고 그 다음 '접두사로 시작하는 요소'를 찾았다면, 

역으로 검색도 가능하다. 요소 -> 접두사 만들어가며 접두사의 존재 여부를 검색.! 먼저 phonebook의 숫자 요소로부터, 앞에서부터 한 글자씩을 더해가면서 접두사를 만들고, 그것이 해시에 있는지를 확인하면 되는 것이다.

만약 접두사가 있다면, 접두사가 겹치는 숫자가 존재하는 것이므로 바로 false가 된다. 

효율성 통과, 해시까지 사용 가능했다.

def solution(phone_book):
    phone_book.sort()
    
    phone_hash = {}
    for i in phone_book : 
        phone_hash[i] = 1 #의미 없고, 중복도 없으므로 1
    
    for number in phone_hash : 
        prefix = ''
        for digit in number : 
            prefix += digit
            if prefix in phone_hash and prefix != number : #  전체 전화번호와 일치하는 접두사 걸러내기
                return False
    return True

 

---

 

Question2 - [챌린저] 베스트 앨범

 

문제설명 https://school.programmers.co.kr/learn/courses/30/lessons/42579