프로그래머스 코테고득점kit

해시 - 전화번호 목록

1. 문제 설명

2. 입출력 예제
   

순회하면서 element의 길이만큼 slicing해서 문자열을 비교하는 방법

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

또는 startswith() 이용한 방법 + hashMap

    ...
    for i in range(len(phone_book)):
        for j in range(i+1,len(phone_book)):
            if dic[i].startswith(dic[j]) or dic[j].startswith(dic[i]):
                return False
    return True   

이중 for문을 사용하므로 복잡도가 커져서 시간효율성이 낮다는 문제가 있다.
어떻게 개선할 수 있을까?

여러 테스트케이스를 입력하다가 놀라운 걸 사실을 알게되었다.
문자형 숫자를 sort할 경우 숫자의 크기가 아니라 숫자의 순서가 정렬의 기준였다.

before : ["40","72","12","123","408"] -- sort -->['12', '123', '40', '408', '72']

따라서 위의 코드를 아래처럼 고칠 수 있다. 불필요한 for문을 제거하였다.

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

배열로 풀었지만, 이 문제는 사실 해시 카테고리에 속한 문제여서

검색을 통해 찾은 해시 solution이다.

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

phoneBook.sort()은 phoneBook의 값을 바꾸고
sorted(phoneBook)은 새로운 배열을 반환한다는 차이가 있다.

zip은 pythond의 내장함수인데,
여러 개의 iterable자료형들을 묶어서 새로운 iterable 자료형을 생성한다. 여기에서 말하는 interable자료형은 리스트, 튜플 같이 반복 가능한 자료형이다.