[프로그래머스/스터디 0주차] 해시 전화번호 목록 Lv.2 - 파이썬(Python)/ sort(key=len), Hash, Zip

 

📑 문제

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

입출력 예 설명

입출력 예 #1
앞에서 설명한 예와 같습니다.

입출력 예 #2
한 번호가 다른 번호의 접두사인 경우가 없으므로, 답은 true입니다.

입출력 예 #3
첫 번째 전화번호, “12”가 두 번째 전화번호 “123”의 접두사입니다. 따라서 답은 false입니다.

 

 

 

 

 

 

 

✒️ 풀이 (2021.08.03)

첫 번째 코드

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

 

 이것도 물론 뭐 참고하면서 겨우겨우 짠 코드다. 하....ㅠ

 하나 배운 것은 파이썬에서 배열 정렬을 할 수 있다는 점이다.

 

list.sort()

 

 

 sort()를 쓰면 숫자 크기로 정렬되는데, 문자열이라도 값의 크기대로 정렬해준다. 자바를 생각하면 충격적이다(ㅋㅋ)

 예를 들어 ["123", "99", "125", "1234", "22456"]이 있다고 하면 ["123", "1234", "125", "22456", "99"] 이렇게 정렬이 된다.

 

list.sort(key=len)

 

 key로 len, 즉 길이를 주면 길이를 오름차순으로 정렬해준다. 위의 예를 들자면 ["99", "123", "125", "1234", "22456"]이 되겠다.

 

 아무튼 이건 하나 배워간 점이고, phone_book을 값의 크기대로 정렬하면, 만약 뒤의 숫자가 앞의 숫자를 접두어로 가지고 있을 때 무조건 인접해 있을 수 밖에 없게 된다. 따라서 인접값만 보면 된다...

 

 

 

 

Hash 함수 이용

def solution(phone_book):
    hashes = {} #혹은 dict()
    for phone in phone_book:
        hashes[hash(phone)] = phone;

    for phone in phone_book:
        temp = ""
        for nums in phone:
            temp = temp + nums
            if hash(temp) in hashes and temp != phone:
                return False
    return True

 

 이건 바로 어제 풀었던 '완주하지 못한 선수' 문제에서 나타난 해시 풀이와도 비슷하다.

 배열에 하나하나 존재하는지 확인하는 것보다, 특정 Hash값이 해시에 있느냐!를 보는 것이 더 빠른 듯 했다 

 

 아무튼 이것도 어렴풋이 접근했던 방법이긴 했는데 너무 가는 것 같아서 안했더니...맞는 풀이었나보다.

 이중 for문을 돌아서 효율성에서 탈락하지 않나?했는데 Hash 덕분인지 안그러는 것 같았다. 알다가도 모를 코테...

 

 

 

zip 함수 이용

def solution(phoneBook):
    phoneBook.sort()
    for p1, p2 in zip(phoneBook, phoneBook[1:]):
    # phoneBook의 마지막 원소는 묶이는게 없이 사라진다.
        print(p1, p2)
        if p2.startswith(p1):
            return False
    return True

 

 zip..zip...어제부터 나를 알쏭달쏭하게 만드는 zip!

 zip은 같은 위치에 있는 것들끼리 묶어주는 함수로 보인다.

 

arr1 = ["apple", "banana", "crocodile"]
arr2 = ["hello", "world"]
arr3 = ["blue", "yellow"]

for zip in zip(arr1, arr2, arr3):
    print(zip)
    
    
# 출력 결과
# ('apple', 'hello', 'blue')
# ('banana', 'world', 'yellow')

 

 위처럼 예시를 짜 돌려봤더니 훨씬 이해가 쉽다.

 같은 위치끼리 묶이는데, 만약 같은 위치에 존재하지 않는 원소("crocodile")가 있다면, 이 원소는 휘발되어 버린다.

 

 for문에서 zip말고 세 변수 a,b,c를 둔다면 튜플로 묶인 각 원소들이 하나씩 a,b,c에 들어가게 된다.

 이 코드에서 알고 가야할 가장 중요한 함수!!!!

 

 

 

startswith() 함수 이용

 

 세상에 이런 함수가 있다니...따로 나중에 정리를 하겠지만 간단하게만 말하자면 특정 문자열이 특정 문자로 시작하는지를 확인할 수 있는 함수이다. True나 False를 반환한다.

str = "가나다라마바하"
>> str.startswith("가")
>> True

>> str.startswith("마", 4)	// 시작 인덱스 지정 가능
>> True

 

 위와 비슷하게 문자열에서 특정 조건을 찾는 함수로는 find(), endswith()이 있지만 나중에 다뤄보겠다.....

 

 

 

 

 

 

 

 

 

🙋‍♀️ 의견 (2021.08.03)

 

 

 휴...진짜 코테 너무 어렵다. 무엇보다 내가 못하는걸 남들에게 보여줘야 하니까 쪽팔린다ㅠ.ㅠ

 자극은 확실히 되어서 이렇게 매일 밤을 고생하게 되긴 하지만, 정신적으로 힘들다...

 내가 짠 코드는 하도 엎어서 저렇게 66점을 맞았던 코드는 지금 찾으려니 기억나지 않는다.

 다만 if문에서 맞으면 바로 return하게 했더니 10점이 올랐던 기억이 있다.

 리턴...꼬박꼬박 잘시키자. 엄한 계산 시키지 말고.

 

 

 

 

 

 

💻 소스코드: 파이썬(Python)

(1)

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

 

(2)

def solution(phone_book):
    answer = True
    dic = {}
    
    for phone_number in phone_book:
        dic[phone_number] = 1
    for phone_number in phone_book:
        temp = ""
        for number in phone_number:
            temp += number
            if temp in dic and temp != phone_number:
                answer = False
                
    return answer

 

 

 

 

 

 

 

 

 

 

 

💎 💎 💎

 

 

Ｐｏｓｔｅｄ Ｂｙ ＳＡＹ

𝘛𝘩𝘢𝘯𝘬𝘴 𝘧𝘰𝘳 𝘳𝘦𝘢𝘥𝘪𝘯𝘨