주제 - “알고리즘 (해시) - 2”

부제 - 프로그래머스 코딩테스트 연습 - 파이썬

출처 - 프로그래머스 - 코딩테스트 연습 - 해시 - 전화번호 목록

​ - 문제의 풀이는 다른 사람의 풀이 중 공부하고 싶은 것을 스크랩한 것입니다.

문제 2. 전화번호 목록

[문제 설명]

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

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

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

[제한사항]

• phone_book의 길이는 1 이상 1,000,000 이하입니다.
• 각 전화번호의 길이는 1 이상 20 이하입니다.

[입출력 예]

풀이

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

풀이의 포인트

phone_book 리스트의 값을 두개씩 비교하여, 한 값이 다른 한 값의 접두어가 되는 경우를 확인하는 문제입니다.

접두어가 될 수 있는 번호는 phoneBook 리스트에서 어느 위치에든지 존재할 수 있습니다. phoneBook 리스트가 정렬된 상태라는 조건이 없기 때문입니다. 접두어가 될 수 있는 번호는 상대적으로 작은 크기일 것이기에, 우선 리스트의 값을 오름차순으로 정렬해야 합니다.

1) 내장함수 sorted : iterable한 입력값을 정렬한 후 그 결과를 리스트로 리턴하는 함수

iterable : 한 번에 하나의 member를 리턴 가능한 object 또는 __iter()__이나 __getitem__() 을 써서 정의한 모든 클래스의 object들

ex) list, str, tuple, dict, file 등

>>> a = 'cocojelly'
>>> dir(a)
['__add__', '__class__', '__contains__', '__delattr__', '__dir__', '__doc__', '__eq__', '__format__', '__ge__', '__getattribute__', '__getitem__', '__getnewargs__', '__gt__', '__hash__', '__init__', '__init_subclass__', '__iter__', '__le__', '__len__', '__lt__', '__mod__', '__mul__', '__ne__', '__new__', '__reduce__', '__reduce_ex__', '__repr__', '__rmod__', '__rmul__', '__setattr__', '__sizeof__', '__str__', '__subclasshook__', 'capitalize', 'casefold', 'center', 'count', 'encode', 'endswith', 'expandtabs', 'find', 'format', 'format_map', 'index', 'isalnum', 'isalpha', 'isdecimal', 'isdigit', 'isidentifier', 'islower', 'isnumeric', 'isprintable', 'isspace', 'istitle', 'isupper', 'join', 'ljust', 'lower', 'lstrip', 'maketrans', 'partition', 'replace', 'rfind', 'rindex', 'rjust', 'rpartition', 'rsplit', 'rstrip', 'split', 'splitlines', 'startswith', 'strip', 'swapcase', 'title', 'translate', 'upper', 'zfill']

sorted 사용 예시

>>> a = 'cocojelly'
>>> sorted(a)
['c', 'c', 'e', 'j', 'l', 'l', 'o', 'o', 'y']

>>> a = [12,123,1235,567,88]
>>> sorted(a)
[12, 88, 123, 567, 1235]

>>> a = ({'c': 2, 'l': 3, 'k': 0})
>>> sorted(a)
['c', 'k', 'l']

phoneBook 리스트의 값을 오름차순으로 정렬하기 위해 sorted를 사용합니다.

>>> phoneBook = [12,123,1235,567,88]

>>> phoneBook = sorted(phoneBook)
>>> phoneBook
[12, 88, 123, 567, 1235]

2) 내장함수 zip: 각 iterable의 element들을 모아 iterator를 만드는 함수

iterator : 데이터 스트림을 표현하는 object.

• iterator의 __next__()를 반복적으로 호출하거나 내장함수 next() 의 인자로 넘겨줬을 때, 스트림에 있는 항목을 차례로 리턴

• iterator가 항목을 차례로 리턴하는 것은 for문에서도 사용

• iterator는 반드시 __iter__() 메소드를 가지므로 iterable이기도 함

• 단, 모든 iterable이 iterator인 것은 아님

  

• iterable은 __iter__() 을 사용하여 iterator가 될 수 있음

• 내장함수 iter()를 사용하여 iterator을 생성가능

ex)

>>> a = 'cocojelly'
>>> next(a)
Traceback (most recent call last):
  File "<pyshell#22>", line 1, in <module>
    next(a)
TypeError: 'str' object is not an iterator
    
>>> b = a.__iter__()
>>> type(b)
<class 'str_iterator'>

>>> c = iter(a)
>>> type(c)
<class 'str_iterator'>


>>> a = ({'c': 2, 'l': 3, 'k': 0})
>>> next(a)
Traceback (most recent call last):
  File "<pyshell#31>", line 1, in <module>
    next(a)
TypeError: 'dict' object is not an iterator
    
>>> b = a.__iter__()
>>> type(b)
<class 'dict_keyiterator'>
>>> b
<dict_keyiterator object at 0x00000179C3E976D8>

>>> next(b)
'c'
>>> next(b)
'l'
>>> next(b)
'k'
>>> next(b)
Traceback (most recent call last):
  File "<pyshell#37>", line 1, in <module>
    next(b)
StopIteration

zip 사용 예시

>>> a = 'coco'
>>> b = 'jelly'

>>> z = zip(a, b)

>>> next(z)
('c', 'j')
>>> next(z)
('o', 'e')
>>> next(z)
('c', 'l')
>>> next(z)
('o', 'l')

앞에서 phoneBook 리스트를 sorted로 정렬했으니, 다음은 앞에서부터 2개씩 짝을 이뤄 값을 비교해봐야 합니다. 여기서 zip은 리스트의 값을 앞에서부터 2개씩 묶는 역할을 수행합니다. 기존의 phoneBook 리스트와, phoneBook을 인덱스 1번부터 시작한 리스트를 인자로 zip을 수행합니다.

>>> phoneBook
[12, 88, 123, 567, 1235]

>>> zipped = zip(phoneBook, phoneBook[1:])
>>> zipped
<zip object at 0x00000179C3E8E988>

>>> next(zipped)
(12, 88)
>>> next(zipped)
(88, 123)
>>> next(zipped)
(123, 567)
>>> next(zipped)
(567, 1235)

3) str.startswith(prefix): 문자열 str이 prefix로 시작하면 True를, 그렇지 않으면 False를 리턴하는 string 메소드

str.startswith 사용 예시

>>> a = 'cocojelly'

>>> a.startswith('c')
True

>>> a.startswith('cb')
False

따라서 이를 이용해 위에서 zip을 이용해 묶었던 쌍들을 확인하여, 큰 수의 시작이 작은 수인지를 확인하면 됩니다. 단, startswith는 str 타입에만 사용할 수 있으니, str()을 사용하여 int형의 숫자를 str형의 문자로 바꾸어주어야 합니다.

>>> p1
12
>>> p2
123

>>> p1=str(p1)
>>> type(p1)
<class 'str'>

>>> p2=str(p2)
>>> p2
'123'

>>> print(p2.startswith(p1))
True

iterator에서 next를 이용해 값을 하나씩 리턴받았던 것은 아래와 같이 for문에서도 동일한 원리로 동작합니다. 따라서 적절한 for문 사용을 통해 phoneBook에서 생성될 수 있는 각 쌍을 확인하여, 문제에서 요구하는 결과를 도출할 수 있습니다.

>>> phoneBook
[12, 88, 123, 567, 1235]

>>> zipped = zip(phoneBook, phoneBook[1:])

>>> for i in zipped:
    	print (i)

(12, 88)
(88, 123)
(123, 567)
(567, 1235)

이전 - [프로그래머스 - 코딩테스트 연습] 해시 (1)

이어서 - [프로그래머스 - 코딩테스트 연습] 해시 (3)