해시 테이블 (Hash Table)

해시 테이블에 대해 이어서 더 알아보았다.

LeetCode 706.Design HashMap

다음의 기능을 제공하는 해시맵을 디자인하라.

Solution 1 개별 체이닝 방식을 이용한 해시 테이블 구현

이전 글에서 다뤘던 내용 중 해시 테이블을 디자인 하는 방법에는 2가지가 있었다. 하나는 개별 체이닝 방식이었고, 하나는 오픈 어드레싱 방식이었다. 이 중 개별 체이닝 방식을 통해 해결해보았다.

우선 연결 리스트를 사용하기 위해 ListNode 클래스를 정의해줘야 한다.

class ListNode(object):
    def __init__(self,key = None,value=None):
        self.value = value
        self.key = key
        self.next = None

그리고 난 뒤에 MyHashMap클래스의 초기화 함수를 작성해야 한다. 기본 사이즈를 1000 정도로 지정해주고, key값에 해당하는 value가 없을 경우 에러 발생을 막기 위해 collections.defaultdict(ListNode)를 사용하여 선언해줘야 한다. defaultdict의 인자로는 앞서 선언한 ListNode 클래스를 넣어 기본값이 연결 리스트로 생성되도록 한다.

def __init__(self):
        self.size = 1000
        self.table = collections.defaultdict(ListNode)

이 문제에서는 편의상 해시값을 key % self.size를 통해 구하도록 하였다. 이와 같은 모듈로 연산을 통한 해싱은 해시 테이블의 가장 기본적인 해싱 방식이기도 하다. 해싱한 결과인 index는 테이블의 인덱스가 된다.

index = key % self.size
if self.table[index].value is None:
	self.table[index] = ListNode(key,value)
	return

위의 코드처럼 해당 인덱스에 아무것도 없다면 key, value를 삽입하고 바로 종료한다. 이때 self.table[index] is None으로 비교하지 않고 self.table[index].value is None으로 비교하는 이유는 이 해시 테이블을 defaultdict(ListNode)로 선언했기 떄문이다. defaultdict는 존재하지 않는 key, value에 대한 조회를 시도할 경우 에러를 발생시키지 않고 디
책을 보기 전에 혼자 풀어보았다.

class Solution:
    def numJewelsInStones(self, jewels: str, stones: str) -> int:
        freq=collections.defaultdict(int)
        for i in range(len(stones)):
            freq[stones[i]]+=1
        answer=0
        for i in range(len(jewels)):
            answer+=freq[jewels[i]]
        return answer

Solution 1 해시 테이블을 이용한 풀이

이 문제는 stones의 각각의 개수를 헤아린 후, jewels의 각 요소를 키로 하는 각 개수를 합산하면 해결할 수 있다. 따라서 해시 테이블로 풀이할 수 있는 전형적인 문제이다.

우선 freq라는 해시 테이블을 선언하고 stones를 문자 단위로 하나씩 살펴보며 처음 등장한 문자라면 1을 선언하고, 기존에 있던 문자라면 1을 더하여 freq를 만들어간다.

마지막으로 freq의 key가 jewels에 포함될 경우에 해당 value를 count에 더해주면 된다.

class Solution:
    def numJewelsInStones(self, jewels: str, stones: str) -> int:
        freqs={}
        count=0
        
        for char in stones:
            if char not in freqs:
                freqs[char] = 1
            else:
                freqs[char] += 1
        for char in jewels:
            if char in freqs:
                count += freqs[char]
        return count

Solution 2 defaultdict를 이용한 비교 생략

defaultdict를 이용하면 Solution 1에서의 비교 구문을 생략할 수 있다.

class Solution:
    def numJewelsInStones(self, jewels: str, stones: str) -> int:
        freqs=collections.defaultdict(int)
        count=0
        
        for char in stones:
            freqs[char] += 1
        for char in jewels:
            count += freqs[char]
        return count

내가 처음에 혼자 풀어봤던 풀이와 매우 비슷하다.

Solution 3 Counter로 생략

Counter를 사용하면 코드를 더욱 짧게 줄일 수 있다. 각 개수를 계산하는 부분까지 자동으로 처리할 수 있기 때문이다.

class Solution:
    def numJewelsInStones(self, jewels: str, stones: str) -> int:
        freqs=collections.Counter(stones)
        count=0
        for char in jewels:
            count+=freqs[char]
        return count

Counter는 존재하지 않는 키의 경우 KeyError를 발생하는 대신에 0을 출력하기 때문에 defaultdict와 마찬가지로 에러에 대한 예외 처리를 할 필요가 없다. 단순히 jewels에 포함된 문자의 개수를 계산하기만 하면 된다. 실행 속도 또한 동일하다.

Solution 4 파이썬다운 방식

해시 테이블과는 관련이 없지만 이 문제는 파이썬 다운 방식으로 단 한줄로 계산할 수 있다.

class Solution:
    def numJewelsInStones(self, jewels: str, stones: str) -> int:
        return sum(s in jewels for s in stones)

코드 줄 수는 단 한줄이다. 정말 간단하게 풀이가 가능하다. 이 코드는 리스트 컴프리헨션을 출력해보면 직관적으로 이해할 수 있다.

>>> [s for s in stones]
['a', 'A', 'A', 'b', 'b', 'b', 'b']

이는 문자열의 각 문자를 하나씩 출력하는 리스트 컴프리헨션이다.

>>> [s in jewels for s in stones]
[True, True, True, False, False, False, False]

이렇게 약간의 비교 구문을 추가하면 s가 jewels에 포함되어 있는지 여부를 출력할 수 있다. 포함이 되어있다면 True, 아니라면 False가 출력된다. 여기에 sum()함수를 이용하면 True의 개수를 반환하게 된다.

LeetCode 3.Longest Substring Without Repeating Characters

중복 문자가 없는 가장 긴 부분 문자열의 길이를 리턴하라.

Solution 1 슬라이딩 윈도우와 투 포인터로 사이즈 조절

입력값이 s="abcabcbb"인 경우를 살펴보면 슬라이딩 윈도우로 한 칸씩 우측으로 이동하면서 윈도우 내에 모든 문자가 중복이 없도록 투 포인터로 윈도우 사이즈를 조절하면서 풀이할 수 있다.

이 경우 세번째부터 길이가 3으로 최대 길이가 되며, 이 길이는 여섯번째까지 변경 없이 게속 유지된다. 결과적으로 정답은 3이 된다.

코드로 이 과정을 구현하면 투 포인터로 문제를 풀이하되 포인터 2개 모두 왼쪽에서 출발한다. 각각 왼쪽 시작점에서 출발하여 두번째 포인터는 오른쪽으로 계속해서 확장한다.

for index, char in enumerate(s):
    if char in used:
        start = used[char]+1
    else:
    	...

여기서 만약 이미 등장한 문자라면 used에 있을 것이고 이 경우 첫번째 포인터인 start를 used[char]+1 위치로 갱신한다. 등장하지 않았던 처음보는 문자라면 다음과 같이 처리한다.

for index, char in enumerate(s):
    if char in used:
    	...
    else:
    	...
        used[char] = index

이제 used[char]는 현재 문자를 키로 하는 해시 테이블이며 여기에는 현재 위치를 값으로 삽입한다. 즉 start=used[char]+1은 현재위치+1이 되고, 이미 등장했던 문자인 경우에는 왼쪽 포인터인 start를 현재 위치까지 옮기는 것이다. 그러나 이미 등장했다고 무작정 옮기면 문제가 된다. 현재 슬라이딩 윈도우의 바깥에 있는 문자는 예전에 등장한 적이 있어도 지금은 무시해야 하기 때문이다. 따라서 비교 구문에 다음과 같이 and 이후에 조건 start<=used[char]이 추가되어야 한다.

for index, char in enumerate(s):
    if char in used and start<=used[char]:
        ...
    else:
    	...

이렇게 하면 슬라이딩 윈도우 안쪽에 있는 중복 문자에 대해서만 True 처리된다.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        used={}
        max_length = start = 0
        for index, char in enumerate(s):
            if char in used and start <= used[char]:
                start = used[char]+1
            else:
                max_length = max(max_length, index-start+1)
            used[char] = index
        return max_length

LeetCode 347.Top K Frequent Elements

상위 k번 이상 등장하는 요소를 추출하라.

Solution 1 Counter를 이용한 음수 순 추출

요소의 값을 key로 갖는 해시 테이블을 만들고 여기에 빈도 수를 value로 저장한 후 우선순위 큐를 이용하여 추출하면 k번 이상 등장하는 요소를 쉽게 추출할 수 있다. 우선순위 큐는 힙을 활용하는 heapq모듈을 사용한다. 빈도수 freqs는 collections.Couter(nums)를 통해 구해준다.

freqs를 heapq에 넣어줄 차례이다. heapq는 기본적으로 오름차순 정렬이 되도록 삽입되기 때문에 freqs의 value를 음수로 넣어 오름차순이 반대로 들어가도록, 즉 내림차순으로 들어가도록 한다. 이는 최소힙을 최대힙으로 사용하는 방법이다.

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        freqs=collections.Counter(nums)
        freqs_heap = []
        for f in freqs:
            heapq.heappush(freqs_heap, (-freqs[f], f))
        topk=list()
        for _ in range(k):
            topk.append(heapq.heappop(freqs_heap)[1])
        return topk

Solution 2 파이썬다운 방식

상위 k번만큼의 요소를 추출하기 위해 힙에 넣고 빼는 작업을 진행하였다. 이 작업을 자동으로 하는 파이썬의 함수가 존재한다. Counter에는 most_common()이라는 빈도 수가 높은 순서대로 아이템을 추출하는 기능을 제공하는 함수가 존재한다.

>>> collections.Counter(nums).most_common(k)
[(1, 3), (2, 2)]

여기에서 정답인 1과 2를 추출하기만 하면 된다. 여기서는 파이썬의 2가지 기능인 zip()와 *를 활용해본다.

>>> list(zip(*collections.Counter(nums).most_common(k)))[0]
[1, 2]

이와 같은 방법을 이용하면 바로 정답을 구할 수 있다.

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        return list(zip(*collections.Counter(nums).most_common(k)))[0]

zip() 함수

zip() 함수는 2개 이상의 시퀀스를 짧은 길이를 기준으로 일대일 대응하는 새로운 튜플 시퀀스를 만드는 역할을 한다.

>>> a = [1, 2, 3, 4, 5]
>>> b = [2, 3, 4, 5]
>>> c = [3, 4, 5]
>>> zip(a, b)
<zip object at 0x105b6d9b0>

파이썬 2는 zip()의 결과가 바로 리스트가 되지만 파이썬 3에서는 제너레이터를 리턴한다. 제너레이터에서 실잿값을 추출하기 위해서는 list()로 한번 묶어 주면 된다.

>>>list(zip(a, b))
[(1, 2), (2, 3), (3, 4), (4, 5)]
>>>list(zip(a, b, c))
[(1, 2, 3), (2, 3, 4), (3, 4, 5)]

zip()을 통한 결과는 시퀀스가 아닌 튜플이기 때문에 값을 변경하는 것이 불가능한 불변 객체이다. 그렇기 때문에 값을 변경하려고 하면 에러가 발생한다. 여러개의 시퀀스를 가지고 zip() 함수를 적용하면 다음과 같이 적용된다.

>>> a=['a1', 'a2']
>>> b=['b1', 'b2']
>>> c=['c1', 'c2']
>>> d=['d1', 'd2']
>>> list(zip(a, b, c, d))
[('a1', 'b1', 'c1', 'd1'), ('a2', 'b2', 'c2', 'd2')]

a, b, c, d 각각의 리스트가 2개의 튜플로 묶였다.

아스테리스크(Asterisk: *)

zip()의 파라미터는 1개가 될 수도 있고, 2개, 10개가 될 수도 있다. 이렇게 할 수 있는 이유는 바로 아스테리스크를 활용하기 때문이다. 이는 C에서 사용하는 포인터로 착각할 수 있는데 전혀 다른 동작을 수행하고 있다. 파이썬에서는 언팩(Unpack)의 역할을 한다. 시퀀스 언패킹 연산자로 말 그대로 시퀀스를 풀어 헤치는 연산자를 뜻한다. 주로 튜플이나 리스트를 언패킹하는데 사용한다. 바로 전에 풀어보았던 LeetCode 347번의 코드에서 언패킹을 했을 때와 하지 않았을 때의 차이를 비교해보려고 한다.

>>> collections.Counter(nums).most_common(k)
[(1, 3), (2, 2)]
# 언패킹을 했을 때
>>> list(zip(*collections.Counter(nums).most_common(k)))[0]
[(1, 2), (3, 2)]
# 언패킹을 하지 않았을 때
>>> list(zip(collections.Counter(nums).most_common(k)))[0]
[((i, 2), ), ((3, 2), )]

언패킹을 하지 않은 경우 튜플이 풀어지지 않고 그대로 하나의 값처럼 묶였다. 이 경우 언패킹 적용해주어야 튜플의 값을 풀어 헤칠 수 있다. 언패킹한 값만 별도로 출력할 수 없기 때문에 디버깅이 어렵지만 내부적으로 튜플이 제거되고 [[1, 3], [2, 2]]와 같은 형태로 모두 리스트로 풀어질 것이다. 이때 zip()으로 묶으면 정상적으로 묶이게 된다. 다른 쉬운 예도 알아보았다.

>>> fruits=['lemon', 'pear', 'watermelon', 'tomato']
>>> fruits
['lemon', 'pear', 'watermelon', 'tomato']

fruits 리스트의 요소값만 출력하고 싶다면 어떻게 해야 할까?

• 하드코딩으로 하나하나 출력

>>> print(fruit[0], fruit[1], fruit[2], fruit[3])
lemon pear watermelon tomato

• for문으로 순회하여 출력

>>> for f in fruits:
        print(f, end=' ')
lemon pear watermelon tomato

• 언패킹을 적용하여 출력

>>> print(*fruit)
lemon pear watermelon tomato

*는 이외에도 많이 활용된다. 언패킹뿐만 아니라 함수의 파라미터가 되었을 때에는 반대로 패킹(Packing)의 역할도 한다. zip()의 파라미터를 여러 개 쓸 수 있다는 얘기 또한 zip() 함수 정의에서 내부적으로 *로 패킹하고 있다는 얘기이기도 하다.

>>> def f(*params):
        print(params)
>>> f('a', 'b', 'c')
('a', 'b', 'c')

이처럼 하나의 파라미터를 받는 함수에 3개의 파라미터를 전달했지만 params 변수 하나로 패킹되어 처리된다. 이는 파이썬3의 print() 동작 원리이기도 하다.

>>> print('a')
a
>>> print('a', 'b')
a b
>>> print('a', 'b', 'c')
a b c

몇 개의 파라미터를 넘기든 모두 처리가 된다. 또 다른 활용도 알아보았다.

>>> a, *b = [1, 2, 3, 4]
>>> a
1
>>> b
[2, 3, 4]
>>> *a, b = [1, 2, 3, 4]
>>> a
[1, 2, 3]
>>> b
4

변수의 할당 또한 *로 묶어서 처리할 수 있다. 일반적인 변수는 값을 하나만 취하지만 *로 처리하게 되면 나머지 모든 값을 취하게 된다. 이 외에도 *는 파이썬에서 많은 곳에 사용된다.

**는 파이썬에서 어떤 역할을 할까? 파이썬에서 *는 튜플 또는 리스트 등의 시퀀스 언패킹 역할을 하고, **는 키/값 페어를 언패킹하는 역할을 한다.

>>> date_info = {'year': '2022', 'month': '01', 'day': '28'}
>>> new_info = {**date_info, 'date': '29'}
>>> new_info
{'year': '2022', 'month': '01', 'day': '29'}

이와 같이 **는 모든 요소를 언패킹할 수 있다. 여기에서 'day': '29'의 새로운 값으로 업데이트도 시도했고 성공적으로 업데이트 된 것을 확인할 수 있다.