프로그래머스 - 전화번호 목록 (고득점Kit_해시) [Kotlin, Python]

문제 설명

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

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

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

제한사항

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

 

나의 접근 방법

먼저 입력되는 리스트를 정렬했다. 정렬하게 되면 접두어일 경우 바로 인접하게 정렬되며 앞의 요소가 뒤의 요소의 접두어가 될 수 있기 때문이다. 그래서 for문을 돌리면 접두어를 쉽게 찾을 수 있다.

코드 1) 정렬하여 반복문으로 해결하는 방법 (Python, Kotlin)

def solution(phone_book):
  # Sort()하여 1중 루프로 해결하는 방법
  phone_book.sort()
  
  for i in range(len(phone_book)-1):
    if phone_book[i+1].startswith(phone_book[i]):
      return False
  return True

아래는 코틀린 코드로 바꿔서 작성해본 코드다. 로직은 같다.

fun solution(phoneBook: ArrayList<String>): Boolean {
    // 정렬하여 1중 루프로 해결하는 방법
    phoneBook.sort()

    for (i in phoneBook.indices) {
        if (phoneBook[i+1].startsWith(phoneBook[i])) {
            return false
        }
    }
    return true
}

 

코드 2) 해시를 사용하여 해결하는 방법 (Python, Kotlin)

구글링을 하다가 다른 분이 해시를 이용해서 해결하는 방법을 포스팅하셨다. 굉장히 자세하고 이해하기 쉽게 설명해놓으셔서 링크를 첨부하겠다. 여기선 코드와 간단 설명만 적도록 하겠다.

먼저 해시맵을 각 문자열이 Key이고 Value가 1인 해시맵으로 초기화한다. 그 후 비교 변수를 하나 만들어 문자열의 문자를 하나씩 더해가면서 비교 변수와 같은 Key가 있는지 검사한다.

def solution(phone_book):
  # Hash를 이용하여 해결
  
  # 1. Hash map을 만든다.
  hash_map = {}
  for item in phone_book:
    hash_map[item] = 1

  # 2. 접두어가 Hash map에 존재하는지 찾는다.
  for item in phone_book:
    jubdoo = ""
    for char in item:
      jubdoo += char
      # 3. 접두어를 찾는다 (기존 번호와 같은 경우 제외)
      # jubdoo라는 Key가 hash_map에 존재하는지 확인한다.
      if jubdoo in hash_map and jubdoo != item:
        return False
  return True

다음은 코틀린 코드로 작성한 것이다. 로직은 동일하다.

/* 전화번호 목록 */

fun solution(phoneBook: ArrayList<String>): Boolean {
    // HashMap을 이용하여 해결하는 방법
    
    // 1. 
    val hashMap = hashMapOf<String, Int>().apply {
        for (number in phoneBook) {
            this[number] = 1
        }
    }

	// 2.
    for (item in phoneBook) {
        var jubdoo = ""
        for (char in item) {
        // 3.
            if (hashMap.containsKey(jubdoo) && jubdoo != item) {
                return false
            }
        }
    }
    return true
}