프로그래머스 코딩테스트 고득점 Kit : 해시

해당 문제는 프로그래머스에서 제공된 문제입니다.

몇개의 기출들을 푼 뒤 이제 프로그래머스 코딩테스트 고득점 kit를 유형별로 모두 풀어보려 한다. 풀면서 괜찮은 문제나 다른 사람들의 괜찮은 풀이방식이 있다면 소개하겠다. 

---

일단 먼저 해시(hash)파트이다. 해시 파트 같은 경우 문제들이 막 괜찮은 편은 아니라고 느껴서 (해시로 풀지않고 다른 방식으로 구현하는 것이 더 좋은 문제들도 있었음), 몇개의 문제에서의 풀이 및 새롭게 알게된 툴(?)들에 대해서 소개하고 다른 사람의 풀이 중 괜찮은 것들에 대해서만 소개하겠다. 

---

 

먼저, 첫번째 문제같은 경우 해시로 풀기보다는 다른 방식으로 접근하기 보다는 sort를 이용하여 푸는 것이 직관적으로 이해가 더 쉽고 시간복잡도에 있어서도 효율적이였다. 사실 이문제에서 얻은 것은 collection 모듈이다. 다른 사람의 풀이를 통해 collection 모듈을 deque를 제외하고 새로 접했는데, 이 중 유용하게 사용할만한 몇개에 대해서 언급하겠다.

[Collection 모듈]

- deque

deque(데크)는 double-ended queue 의 줄임말로 양방향에서 데이터를 처리할 수 있는 queue형 자료구조를 의미한다.

append(x) 데크의 오른쪽에 x를 추가

 

appendleft(x) 데크의 왼쪽에 x를 추가

 

extend(iterable) iterable 인자에서 온 요소를 추가하여 데크의 오른쪽을 확장

 

extendleft(iterable) iterable에서 온 요소를 추가하여 데크의 왼쪽을 확장

 

index(x[, start[, stop]]) 데크에 있는 x의 위치를 반환 (인덱스 start 또는 그 이후, 그리고 인덱스 stop 이전)

 

insert(i, x) x를 데크의 i 위치에 삽입

 

pop() 데크의 오른쪽에서 요소를 제거하고 반환, 요소가 없으면 IndexError를 발생

 

popleft() 데크의 왼쪽에서 요소를 제거하고 반환합, 요소가 없으면 IndexError를 발생

 

remove(value) value의 첫 번째 항목을 제거, 찾을 수 없으면 ValueError를 발생

 

reversed() 데크의 요소들을 순서를 역순으로 뒤집기

 

rotate(n=1) 데크를 n 단계 오른쪽으로 회전, n이 음수이면 왼쪽으로 회전 (linked list의 동작)

 

maxlen 데크의 최대 길이 지정

 

- Counter

컨테이너 값의 동일한 객체가 몇개인지 파악할때 쓰이고 list를 dict로 만들어 갯수를 센다.

elements() dict의 요소를 iter로 풀어서 보여줌

 

most_common() 요소값중 비중이 가장 높은 순으로 반환한다, 값을 입력하면 입력된 값의 빈도수 만 반환한다

 

subtract() 입력된 dict의 요소만큼 빼서 값을 보여준다 #그냥 '-'로 구현가능 → A.subtract() == A-B

 

update() 입력된 dict의 요소만큼 더해서 값을 보여준다 #그냥 '+'로 구현가능 → A.update() == A+B

from collections import Counter
A = Counter(a=1,b=2,c=3,d=4)
B = Counter(['a','a','b','b','c','c','d','d'])

sorted(A.elements()) #A를 리스트로 다시풀어서 보여줌 
# -> ['a', 'b', 'b', 'c', 'c', 'c', 'd', 'd', 'd', 'd']

A-B # 빼고 0이하의 값은 버림
# -> Counter({'d': 2, 'c': 1})
A.subtract(B) # A - B 를 한다음 A에 값을 저장 (0이하의 값도 유지)
# -> Counter({'d': 2, 'c': 1, 'b': 0, 'a': -1})

A+B
# -> Counter({'d': 6, 'c': 5, 'b': 4, 'a': 3})
A.update(B) # A + B 를 한다음 값을 저장
# -> Counter({'d': 6, 'c': 5, 'b': 4, 'a': 3})

A.most_common() #값이 제일 높은순서로 tuple형식으로 보여줌
#->[('d', 4), ('c', 3), ('b', 2), ('a', 1)]

 

- defaultdict 

dict의 서브클래스, dict 와 작동하는 방식은 거의 동일하지만 인자로 주어진 객체의 기본값을 딕셔너리값의 초깃값으로 지정할 수 있다.

int, list, set 등으로 초기화 할 수 있기때문에 여러 용도로 사용 가능, dict와 다르게 키가 없는요소를 불러와도 에러가 나지 않음

from collections import defaultdict
A = defaultdict(int) # int형 dict
A
# -> defaultdict(<class 'int'>, {})
A['a'] # 원래 dict같은 경우였으면 Error이지만, defaultdict같은 경우 0값을 초기값으로 설정해줌
A
# -> defaultdict(<class 'int'>, {'a': 0})

이런 모듈을 알아두면 코드를 더 빠른시간 안에 효율적으로 풀 수 있다. 특히 deque같은 경우 queue를 사용하는 문제에서 list보다 시간복잡도에서 더 효율적이므로 용이하게 사용할 수 있을 것이다.

 

 

두번째 문제에서 나같은 경우 정석으로 풀지 않고, sort()를 이용하여 비교하며 풀어갔다, 시간 복잡도에서도 좋은 결과를 보였지만, 정석으로 푼 코드가 있어서 이에 대해서 소개하려 한다.

def solution(phone_book): 
    answer = True
    hash_map = {} # 해당 요소가 존재하는지 탐색할 때, dict를 사용하여 시간복잡도에서 유리
    # 모든 전화번호를 dict에 저장
    for phone_number in phone_book:
        hash_map[phone_number] = 1
    # 각 전화번호에 대해서 탐색
    for phone_number in phone_book:
        temp = "" # 접두어인 경우를 탐색하기 위한 문자열 저장
        # 해당 전화번호를 앞에서 부터 한글자씩 temp에 저장
        for number in phone_number:
            temp += number
            # 해당 전화번호의 앞부분의 일부를 저장한 temp와 동일한 전화번호가 있는지 판단
            if temp in hash_map and temp != phone_number:
                answer = False
    return answer

이 문제풀이는 일단 요소 탐색을 dict를 이용하여 시간복잡도를 줄이고 전화번호의 앞부분을 순차적으로 잘라가며 기존의 hash_map과의 비교를 통해 판단한다는 아이디어가 좋았던 것 같다.

 

 

세번째 문제는 코드 구현이 어렵다기 보다는 확률에서의 수식적인 부분이 까다로웠던 문제이다. 확률을 공부하지 않았던 사람이라면 좀 까다로울 수 있는 문제였다. (각 의류에 대해 안입는 경우를 포함하여 모든 경우를 다 구한 후, 어떤 의류도 입지 않은 경우 즉, 아무것도 입지않은 상태 만을 빼면 된다). 이 문제에서의 다른 사람들의 풀이를 보면 Counter 나 defaultdict를 유용하게 사용한 경우를 볼 수 있다. Counter를 통해 의류의 종류마다의 개수를 구하여 푼 경우도 있고, defaultdict를 통해 초기값을 따로 설정하지 않고 값들을 누적시키는 경우도 있었다. 이런 것들을 보면 역시 일단 모듈이든 뭐든 많이 알고 있으면 좋은 것 같다.

 

마지막, 네번째 문제는 이 챕터에서 가장 어려운 난이도였다. 문제를 이해하는 데 어려움은 없었지만, 이를 구현하는 데에 시간이 좀 걸렸다. 이 문제에서의 핵심도 역시 시간복잡도였다.

---

[마무리]

일단 해시파트라 그런지 난이도가 높은 편은 아니였지만, 풀이방식이 너무나도 다양하고 풀어도 시간복잡도에서 Fail된 경우가 꽤나 있었다. 요즘은 코드를 구현한다고 다 되는게 아니라 효율적이고 가독성이 있으며 시간복잡도를 줄이는 코딩을 하는 연습이 필요하다고 계속 느낀다.