[파이썬] 전화번호 목록

출처 : 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_book	return
["119", "97674223", "1195524421"	false
["123", "456", "789"]	true
["12", "123", "1235", "567", "88"]	false

 

입출력 예 설명

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

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

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

 

 

🧀 나의 풀이

 

def solution(phone_book):
    phone_book.sort()

    for idx, p in enumerate(phone_book[:-1]):  # 한 번호가
        temp = ''
        another=phone_book[idx+1]
        for i, j in zip(another, p):  # 다른 번호의 접두사인지
            if i == j:
                temp += i
        if temp == p:
            return False
    return True  # 접두어 없음

 

더 쉽게 찾기 위해 정렬을 했다.

인덱스 범위 초과가 날 수 있어서 바깥쪽 for문에서 phone_book의 마지막 값은 제외함

zip을 사용해서 두 문자열의 값을 뽑아내고 비교한다.

반복문이 끝난 후 temp가 접두사 p와 같다면 한 번호가 다른 번호의 접두사인 경우다.

 

 

# 해쉬 이용

def solution(phone_book):
  hash_map ={}      # 딕셔너리
  for phone_number in phone_book:     #요소 반복
    hash_map[phone_number] = 1        #키는 리스트의 요소, 값은 1로 통일.
  for phone_number in phone_book:
    temp = ""
    for number in phone_number:     #한 글자씩
      temp += number
      if temp in hash_map and temp != phone_number:     # 자기 자신이랑 비교 금지.
          return False
  return True

 

딕셔너리는 키, 값의 쌍으로 이루어짐. 키는 중복이 안된다. 리스트의 각 요소들을 키로 정하고 값은 임의로 1.

두번째 for문에서는 phone_book 리스트에 있는 요소를 꺼낸다. 한 글자씩 temp에 덧붙여간다.

hash_map 딕셔너리에 temp가 있고 temp와 phone_number가 다르다면 false를 리턴한다. (즉 한 번호가 다른 번호의 접두사인 경우를 찾았을 때임.)

 

 

🍋 다시 풀어봄~

# 효율성에서 실패
def solution(phone_book):   # 전화번호
    for i, p in enumerate(phone_book) :
        for j in range(i+1, len(phone_book)) :   # 인덱스
            for x, y in zip(p, phone_book[j]) :
                if x != y :
                    break
            else :  # 접두어
                return False
                
    return True   #  어떤 번호가 다른 번호의 접두어인 경우가 있으면 false

 

효율성에서 3, 4번 시간초과

phone_book을 오름차순 정렬 후 반복문 돌려도 결과는 똑같네 ㅠ

 

# 성공
def solution(phone_book):   # 전화번호
    phone_book.sort()
    
    for i, j in zip(phone_book, phone_book[1:]) :
        for x, y in zip(i, j) :     # 한 글자씩 비교
            if x != y :
                break
        else :  # 접두어
            return False
                
    return True   #  어떤 번호가 다른 번호의 접두어인 경우가 없음

 

다른 사람 풀이 보면서 for문을 하나 줄일 수 있었다.><

 

 

// 실패
import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        Arrays.sort(phone_book);
        String temp="";
        int len=0;
        
        for(int i=0; i<phone_book.length-1; i++){
            len=phone_book[i].length();
            temp=phone_book[i+1].substring(0, len);
            if(phone_book[i].equals(temp)){
                return false;
            }
            }
        return answer;
    }  
    }

 

제출하니 런타임에러 뜨는 케이스가 몇개 있음..

 

 

🍿 다른 사람 풀이

 

def solution(phone_book):
    phone_book=sorted(phone_book)
    
    for p1, p2 in zip(phone_book, phone_book[1:]) :
        if p2.startswith(p1) :	# 접두사면
            return False
    return True

 

phone_book을 정렬한다.

p2.startswith(p1)은 p2에 접두사로 p1이 있으면 True 반환.

 

😎 알게된 점

for p1, p2 in zip(phone_book, phone_book[1:]) :

나는 아래처럼 했는데 zip을 쓰고 슬라이싱하면 더 간단하게 할 수 있구나.

for i, p in enumerate(phone_book) :
        for j in range(i+1, len(phone_book)) : 

 

 

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        for(int i=0; i<phone_book.length-1; i++){
            for(int j=i+1; j<phone_book.length; j++){
                if(phone_book[i].startsWith(phone_book[j])){
                    return false;
                }
                if(phone_book[j].startsWith(phone_book[i])){
                    return false;
                }
            }
        }
        return true;
    }  
    }

 

startsWith를 사용하면 쉽게 접두사인지 아닌지를 판단할 수 있다.

 

 

 

문제 출처 👉 프로그래머스