[Python] 코딩테스트 고득점Kit | 해시2- 전화번호 목록

아래의 문제는 프로그래머스 코딩테스트 고득점 Kit 내용이며 코드는 직접 푼 내용입니다.

---

전화번호 목록

문제상황

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인

 

요구사항

전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때,

어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성

 

제한사항

• phone_book의 길이는 1 이상 1,000,000 이하입니다.
  • 각 전화번호의 길이는 1 이상 20 이하입니다.
  • 같은 전화번호가 중복해서 들어있지 않습니다.

입출력

첫번째 케이스의 경우, 첫번째 전화번호,"119"가 세번째 전화번호 " 1195524421"의 접두라사 false

두번째 케이스의 경우, 한 번호가 다른 번호의 접두사인 경우가 없으므로, 답은 true

세번재 케이스의 경우, 첫 번째 전화번호, “12”가 두 번째 전화번호 “123”의 접두사라  false 

---

풀이과정

일단, 해쉬에 각 숫자들을 넣음.  그래서 그 해쉬의 value를 통해서 접두사인지 체크해보려는 목적

접두사인지 파악해보기 위한 tmp 문자열이 필요함

이 tmp문자열은 다시 리스트들을 탐색하면서 문자열을 합침.

그 tmp가 해쉬에 있으면 접두사(false)고 없으면 접두사가 아닌걸로 true

 

결과

어느정도 어떻게 풀지는 생각을 했지만 문자열이 접두사인지 체크해보는 부분을

코드로 구현하는데 어려워서 참고를 했다. 

def solution2(phone_book):
    dict={}
    for phone_num in phone_book:
        dict[phone_num] = 1
    print(dict) #{'119': 1, '97674223': 1, '1195524421': 1}

    for phone_num in phone_book:
        tmp =""
        for num in phone_num:
            tmp+=num
            print(tmp)
            if tmp in dict and tmp!=phone_num:
                return False
    return True

• phone_book : 맨처음에 입력받은 리스트 ["119", "97674223", "1195524421"]
• phone_num : 리스트의 원소하나하나 119
• num : 그 원소의 문자열 하나 1 
• tmp : tmp+=num으로 문자열 하나하씩 다시 이어붙임 1 ->11 -> 119 
• if tmp in dict and tmp!=phon_num : 맨처음 등록한 해쉬에 있는지 그리고 자기자신이 아닌지 검사

위에 접두사인지 확인해볼때 tmp를 출력해봤는데 이랬다.

그러니까 문자열을 한글자씩 잘라 이어붙이면서 dict에 있는지 확인해보는 것이다. 

그러다가 1195524421 문자열을 검사해보다가 119가 나올때

    if tmp in dict and tmp!=phone_num: 에 걸려서 dict에 있으니까 false로 종료가 된다. 

 

다른풀이

이렇게 정석대로 hash를 쓰는게 아닌 아이디어 방식

생각해보면 '접두사'인지를 확인하는 것이기 때문에 정렬하고 나면 반드시 비교할 두 문자열이 붙어 있을 것이다.

이 생각을 응용해서 zip과 startswith를 사용한다. 

def solution(phone_book):
    answer = True
    phone_book.sort()
    for p1,p2 in zip(phone_book,phone_book[1:]):
        if p2.startswith(p1):
            answer=False
    return answer

이렇게 되면 sort를 해서 비교할 문자열과 다음 문자열은 접두사인지 서로 비교하는 대상이 된다.

예를 들어, ['119', '1195524421', '97674223'] 과 ['1195524421', '97674223'] 이 되는 것이다.

그래서 p2.startswith(p2)으로 접두사인지 시작하는지를 비교한다 

 

배운점

• dict는 있는지 없는지 검사할때 사용할 수 있다. 0,1로 구분해서 있나 없나를 체크하는 목적으로 사용하기 
• zip(객체1, 객체2) : 두 그룹의 데이터를 서로 엮어주는 파이썬의 내장함수 한번에 변수로 쓸 수 있다. 
• p2.startswith(p1): p1문자열안에 p2문자열로 시작하는지 F/T로 리턴하는 함수

 

 

---

참고 

참고한 블로그 링크