99클럽 코테 스터디 5일차 TIL + 해시(Hash) + in 연산자

[오늘의 학습 키워드 및 문제]
- 프로그래머스의 "전화번호 목록" 문제를 풀었다.
- 문제의 주제는 해시였지만, 가장 먼저 떠오른 풀이는 해시가 아니었다. 하하하...
- 하지만 문제의 취지에 맞게 해시로도 풀어보았다.

[나의 코드]

def solution(phone_book):
    answer = True
    phone_book.sort()
    
    for i in range(len(phone_book) - 1):
        if len(phone_book[i]) < len(phone_book[i + 1]):
            if phone_book[i + 1][:len(phone_book[i])] == phone_book[i]:
                answer = False
                break
    return answer

일단 내가 가장 먼저 떠오른 풀이었다.
phone_book[i + 1][:len(phone_book[i])] == phone_book[i]
이 부분을 코드로 먼저 짜서 답이 나오는지 확인해 보고 나머지 코드를 짜기 시작했다.

처음에 왜 코드가 실행이 안될까 싶었는데 sort()가 빠져서 안 됐었다.
코드의 for 루프는 인접한 두 문자열만 비교하니까 sort()를 꼭 넣어야 했다. 난 멍청이다. ^^
그리고 정렬이 없는 경우 모든 쌍을 비교해야 하므로 O(n^2)의 시간 복잡도를 가지게 된다.
반면에 정렬이 있는 경우 O(n log n) + O(n)의 시간 복잡도를 가지므로 더 효율적인 코드가 된다.

def solution(phone_book):
    answer = True
    
    phone_num = {}
    for numbers in phone_book:
        phone_num[numbers] = 1
    
    for numbers in phone_book:
        prefix = "" # 접두어 초기화
        for num in numbers:
            prefix += num # 접두어 하나씩 확인
            
            # 딕셔너리에 접두어가 있고 자기 자신은 셈에서 제외
            if prefix in phone_num and prefix != numbers: 
                return False
            
    return answer

이거는 해시로 푼 풀이다. 딕셔너리는 많이 써보질 않아서 해시는 익숙하지 않은 자료구조다. ㅠㅠ
일단 딕셔너리 만들어서 해시맵을 만들어 준다.

그리고 그 다음부터 뭘 어떻게 할까 좀 고민해봤다. 그런데 쪼만한 내 뇌로는 적절한 풀이가 떠오르지 않아 다른 분들 코드를 참고해서 작성해 봤다.

※ 일단 내가 공부한 것은 딕션너리에서 in 연산자의 사용이었다.
prefix in phone_num 이 부분이다.
딕셔너리에서 in 연산자는 기본적으로 key를 확인하는 데 쓰인다고 한다. (value는 무시된다고.. 쓸 수는 있다고 한다. 개인적으로 딕셔너리를 만든 의도를 엿볼 수 있었다.)

여기서 첫 번째 풀이와 두 번째 풀이의 효율성 차이를 보고 가겠다. (사진 정렬하는 법 몰라서 뻘줌하다.)
음...테스트1, 2는 두 번째 풀이가 더 빠르고 3, 4는 첫 번째가 풀이가 더 빨랐다.
근데 평균적으로는 첫 번째 풀이가 더 빠른 듯하다.

첫 번째 풀이

해시 풀이

 

[오늘의 회고]
- 오늘은 딕셔너리에서 in 연산자의 쓰임에 대해 알아 보았다. in 연산자 별거 아니라 생각했는데 뜯으면 뜯어 볼수록 어렵다. ^^... 오늘도 심오한 컴퓨터의 세계 
- 그리고 오늘 배열 길이가 1,000,000개여서 for문을 2개 돌리면 망할 것 같다는 것만 생각한 것 같다.
- 근데 딕셔너리 많이 안쓰다 보니 자꾸 까먹는다. 다시 공부하러 간다. 끝!