- 반복과 비교 횟수, 그러니까 순회 횟수를 줄일 순 없을까?
- 문제 조건을 내가 검증하는게 아닌 자료구조가 대신 보장하게 할 수 없을까?
- 파이썬 내부에 이 문제에 맞는 문법이 있지 않을까?
이 세가지 관점으로 두 문제를 풀어보았다.
신고 결과 받기 (새 탭에서 열림 / opens in a new tab)
- 리턴: 유저가 신고한 ID중 몇 명이나 실제 정지가 되었는가? (몇개의 메일을 받았는가)
- 신고 규칙
- 유저는 한번에 하나의 유저만 신고 할 수 있다.
- 신고 횟수 제한 없음. 서로 다른 유저를 계속 신고 할 수 있다.
- 한 유저를 여러번 신고 할 수도 있지만, 신고 횟수는 1회로 처리된다.
이 문제에서는 신고 규칙 중에서 아래와 같은 부분을 자료구조가 보장하도록 풀 수 있었다.
한 유저를 여러번 신고 할 수도 있지만, 신고 횟수는 1회로 처리된다.
배열에 저장해서 if문으로 검증하지 말고, 애초에 유저가 신고한 ID를 저장하는 자료구조를 중복을 허용하지 않는 자료구조로 저장하면 된다.
파이썬에서 중복을 허용하지 않는 자료구조는 딕셔너리와 set이 있다.
- 딕셔너리는 key를 해시해서 해당 key가 저장된 위치를 빠르게 찾고, 그 key에 연결된 value를 가져온다.
- set은 원소 자체를 해시해서 해당 원소가 저장되어 있는지 빠르게 확인한다.
- 딕셔너리는 key 중복을 허용하지 않고, set은 원소 중복을 허용하지 않는다.
이렇게 딕셔너리 - set 형태로 신고 리스트를 관리하게 되면 따로 if문으로 중복 검사를 해주지 않아도 된다. 딕셔너리 내부 신고자 ID 집합은 리턴이 '갯수' 이므로 순서도 value도 없이 중복 값만 걸러주는 set이 적당하다.
정답 코드
def solution(id_list, report, k):
mail = {}
reporters = {}
for user in id_list:
mail[user] = 0
reporters[user] = set()
for item in report:
reporter, reported = item.split()
reporters[reported].add(reporter)
for reported in reporters:
if len(reporters[reported]) >= k:
for reporter in reporters[reported]:
mail[reporter] += 1
return list(mail.values())변수명은 x, y로 구현했다가 코드 자체가 길어져서 가독성을 위해 report에 맞춰 수정하였다.
전화번호 목록 (새 탭에서 열림 / opens in a new tab)
- 리턴: True or False
- 한 번호가 다른 번호의 접두어이면 바로 False 반환. 아닐 경우 최종 True 반환.
이 문제에서 순회를 줄이는 법은 단순했다
'문자열 배열이 어떻게 정렬되는가'
를 알고 있다면 바로 O(N²)의 순회를 하는것이 아닌 O(N)- 전체 정렬 비용까지는 O(N log N)의 시간 복잡도를 가진 방법을 떠올릴 수 있었다.
또한 파이썬 내부에 startswith()이라는 메서드가 있었다.
이 메서드는 문자열이 지정된 접두사(특정 문자나 문자열)로 시작하는지 확인하여 True 또는 False를 반환하는 메서드다. 내가 슬라이싱으로 구현한 부분을 임시 배열을 만들지 않고, 가독성 좋게 구현할 수 있게 한다.
string.startswith(prefix, start, end) # prefix만 입력해도 사용가능정답 코드
def solution(phone_book):
phone_book.sort()
for i in range(len(phone_book)-1):
if phone_book[i+1].startswith(phone_book[i]):
return False
return True