[Python] 프로그래머스 전화번호 목록

전화번호 목록

해시를 사용한 문제

 

 

내가 푼 풀이(실패)

while True로 인해 실행시간 초과로 나와서, 중복되는 값들을 제거해 주었음에도 효율성 부분에서 모두 실패가 나왔다.

def solution(phone_book):
    answer = 0
    phone_book.sort()  # 정렬

# 정렬시켜 제일 길이가 작은 문자열을 찾을 접두사 find 로 지정
    find = phone_book[0]
	
    while True:
        v = []
        # 찾을 접두어의 길이만큼 다른 요소들의 값을 슬라이싱해 리스트에 저장
        for i in range(1, len(phone_book)):
            v.append(phone_book[i][:len(phone_book[0])])

        for idx, value in enumerate(v):
            # 찾을 접두사 find와 리스트 안 value가 같다면
            # answer += 1하고, 실행 시간을 위해 중복된 접두어를 가진 값을 제거
            if value == find:
                i = phone_book[idx + 1]
                phone_book.remove(i)
                answer += 1

            else:
                answer += 0
		
        # 다른 접두어를 제거하기 위해 찾기 완료한 접두어를 제거
        phone_book.remove(find)

    if answer != 0:
        return False

    return True

 

 

[다른 풀이 이해하기]

풀이1

해시를 사용한 풀이

해시를 사용하지 않아도 풀 수 있을 것 같아서 제거해 봤는데, 효율성 부분에서 시간초과가 걸렸다.

이 코드 작성하신 분의 의견은 요소를 담아서 있는지 확인하는 부분에서 해시의 속도가 빠른 것 같다고 적어 놓으셨다.

실제로 확인해보니, 해시 연산의 평균 시간복잡도가 O(1)으로 매우 빠른 시간을 가진다.

 

[참고 블로그 ]

해시(Hash) 개념 정리(Feat. 파이썬 알고리즘 인터뷰)

def solution(phone_book):
    ans = True
    hash = {}
    
    # 모든 요소를 (전화번호) {'전화번호' : 1} 형식으로 담는다
    for i in phone_book:
        hash[i] = 1
    
    for i in phone_book:
        tmp = ''
        for j in i:
            tmp += j
            if tmp in hash and tmp != i:   # 담아 높은 hash에서 요소 찾기
                ans = False
    
    return ans

 

 

풀이2

sort 시, key를 이용해 효율성이 높은 풀이

def solution(phone_book):
    phone_book.sort(key=lambda x: len(x)) 	# 길이로 정렬 
    print(phone_book)
    
    for a in range(len(phone_book)): 	# 리스트 기준요소를 반복문 돌리기
        for b in range(a+1, len(phone_book)): 	# 기준 요소의 다음 요소부터 반복문 돌리기 
        # 다음 요소가 기준요소의 길이로 잘랐을때 값이 같으면 false
            if phone_book[b][:len(phone_book[a])] == phone_book[a]: 
                return False
                
    return True

 

 

풀이3

내장함수 zip을 사용한 풀이

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

 

ex)

phone_book = ["12", "123", "1235", "567", "88"]

for p1, p2 in zip(phone_book, phone_book[1:]):
	print(p1, p2)
    
>> 12 123
>> 123 1235
>> 1235 567
>> 567 88

 

 

 

 

---

startswith 함수

startswith(시작하는 문자, 시작 지점)

s = '가나다라 마바사아 자차카타 파하'
s.startswith('가')
>> True

s.startswith('마')
>> False

s.startswith('마',s.find('마')) #find는 '마' 의 시작지점을 알려줌 : 5
>> True

s.startswith('마',1)
>> False

 

 

endswith 함수

endswith(끝나는 문자, 문자열의 시작, 문자열의 끝)

s = '가나다라 마바사아 자차카타 파하'
s.endswith('마')
>> False

s.endswith('하')
>> True

s.endswith('마',0,10)
>> False

s.endswith('마',0,6)
>> True

 

 

zip() 함수

여러 개의 iterable한 객체를 인자로 받아, 각 객체가 담고 있는 원소를 튜플(tuple)의 형태로 반환

 

예제1)

num = [1, 2, 3]
letters = ['A', 'B', 'C']

for pair in zip(num, letters):
	print(pair)
    
>> (1, 'A')
>> (2, 'B')
>> (3, 'C')

 

예제2)

num = [1, 2, 3]
letters = ['A', 'B', 'C']

for i in zip(num, letters):
	pair = (num[i], letters[i])
    print(pair)
    
>> (1, 'A')
>> (2, 'B')
>> (3, 'C')

 

 

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/42577

프로그래머스