아스

* 해당 포스트는 <파이썬 알고리즘 인터뷰> 공부 후 정리 목적으로 작성되었습니다. *

leetcode 46번 ( https://leetcode.com/problems/permutations/ )

풀이 1. (교재 참고)

DFS를 재귀 함수로 사용해서 풀 수 있다. 

이때 지금까지 탐색한 경로(노드)를 저장하는 prev_elements와 최종 탐색한 결과만을 저장하는 results 두 개의 변수를 사용한다. 

dfs() 라는 이 내부 함수는 숫자 리스트를 매개변수로 받는다. 그리고 다음에 탐색할 숫자 리스트를 저장하는 next_elements 변수에다가 매개변수로 받은 리스트 값을 할당한다. 

이때 = 를 사용해서 변수를 그대로 할당하면 파이썬에서는 값을 복사하는 것이 아니라 참조하게 되므로, [:]을 통해 할당해 준다. 

next_elements = elements		# assign by reference
next_elements = elements[:]		# assign by value

for loop를 돌면서 임의로 원소를 하나 빼낸 뒤 next_elements 리스트에서는 해당 원소를 제거한다. 왜냐하면 현재 탐색한 노드(경로)이므로 다음 dfs() 시행에서는 탐색하지 않을 것이기 때문이다. 

반대로 prev_elements 리스트에다가는 해당 원소를 추가한다. 현재 탐색한 노드를 기록해야 하기 때문이다. 

그 다음에 next_elements를 매개변수로 두고 dfs()를 다시 호출한다. 

dfs(next_elements)

dfs()의 재귀적 시행은 다음에 탐색할 노드가 없어지면 종료된다. 종료될 때는 그동안 탐색한 노드 경로를 결과를 저장하는 변수인 results에 할당해 준다. 

마찬가지로 results에 값을 추가할 때는 prev_elements의 값을 참조하지 않고, 복사해서 저장해야 하므로 [:]으로 문자열을 슬라이싱 및 복사해서 사용한다. prev_elements는 재귀적으로 dfs()가 시행되면서 계속 변경되는 값이기 때문이다. 

if len(elements) == 0:
	result.append(prev_elements[:])

이 모든 과정은 dfs()가 한 번 호출되면 이후에는 재귀적으로 시행되므로 처음에 dfs()를 한 번만 호출해 주면 된다. 

다음 예시를 보자. 

nums = [1, 2, 3, 4] 라는 입력이 주어질 때, 출력으로 [1, 2, 3, 4]가 추가되는 경우를 자세히 살펴보자. 

step 1. dfs([1, 2, 3, 4])

elements = [1, 2, 3, 4]

prev_elements = [1]

next_elements = [2, 3, 4]

step 2. dfs([2, 3, 4])

elements = [2, 3, 4]

prev_elements = [1, 2]

next_elements = [3, 4]

step 3. dfs([3, 4])

elements = [3, 4]

prev_elements = [1, 2, 3]

next_elements = [4]

step 4. dfs([4])

elements = [4]

prev_elements = [1, 2, 3, 4]

next_elements = []

step 5. dfs([])

elements = []

len(elements) == 0 이므로 더 이상 dfs()가 호출되지 않고 results 변수에 prev_elements([1, 2, 3, 4])가 추가된다. 

풀이 2. (교재 참고)

파이썬에서 기본으로 제공하는 itertools 모듈을 이용해도 풀 수 있다. 

itertools에서는 여러 메소드를 제공하는데 그 중 하나가 리스트를 매개변수로 받아서 리스트의 원소에 대해 가능한 순열 리스트를 리턴하는 permutations() 메소드이다. 

itertools.permutations(list_name)

permutations() 외에도 가능한 조합 리스트를 리턴하는 combinations(), 중복 조합 리스트를 리턴하는 combinations_with_replacement(), 가능한 cartesian product 경우를 리스트로 리턴하는 product() 등 다양한 메소드가 있다. 

이 모듈을 사용하면 코드를 한 줄로 쓸 수 있다. 

return list(itertools.permutations(nums))

참고한 포스트

https://docs.python.org/3/library/itertools.html#module-itertools

* 해당 포스트는 <파이썬 알고리즘 인터뷰> 공부 후 정리 목적으로 작성되었습니다. *

leetcode 17번 ( https://leetcode.com/problems/letter-combinations-of-a-phone-number/ )

풀이 1. 

재귀함수를 이용해서 풀 수 있다.

딕셔너리를 이용해서 각 digits의 자리수를 key로, 해당 자리수의 문자열 리스트를 value로 저장한다. 

그리고 내부 함수를 선언하여 재귀함수로 사용한다. digits의 맨 뒤의 자리수에서부터 맞는 문자열을 리스트로 리턴하고, 해당 리스트의 앞에다가 붙여 준다. 

digits="234"를 예로 들어보자. 

"3"과 "4"의 관계를 보면, "4"에서는 뒤의 문자열이 더 이상 없어서 딕셔너리에서 "4"에 해당하는 알파벳 리스트인 ["g","h","i"] 값을 불러온다. 

"3"에서는 "4"에서 리턴된 ["g","h","i"]의 각 요소를 for loop로 순회하면서 각 요소의 앞에다가 "3"에 해당하는 알파벳 리스트인 ["d","e","f"]의 각 요소들을 붙여준다. 

전체 코드는 다음과 같다. 

class Solution(object):

    def letterCombinations(self, digits):
        phone = {
            "2": ["a","b","c"],
            "3": ["d","e","f"],
            "4": ["g","h","i"],
            "5": ["j","k","l"],
            "6": ["m","n","o"],
            "7": ["p","q","r","s"],
            "8": ["t","u","v"],
            "9": ["w","x","y","z"]
        }

        def comb(length):
            if length == len(digits)-1:
                return phone[digits[length]]

            result = []
            for i in phone[digits[length]]:
                for j in comb(length+1):
                    result.append(i+j)
            return result

        if digits == "":
            return []
        return comb(0)

* 해당 포스트는 <파이썬 알고리즘 인터뷰> 공부 후 정리 목적으로 작성되었습니다. *

leetcode 200번 ( https://leetcode.com/problems/number-of-islands/ )

풀이 1. 

그래프 탐색 방법 중 DFS를 이용해서 풀 수 있다. DFS와 BFS는 그래프 중 connected components 문제를 푸는 데도 사용된다. 이 문제도 점 하나가 사방의 주변 점과 연결되면 연결된 육지로, 사방이 물이면 개별적인 섬으로 간주하기 때문에 connected component의 개수를 찾는 문제로 볼 수 있다. 

또한 입력이 주어지면 다른 제약 사항이 없는 한 입력을 임의로 바꿔서 풀 수도 있었다. 

이 방법에서는 for loop를 2번 사용해서 입력으로 주어진 grid를 행과 열로 탐색해서 육지(grid[i][j]==1)를 찾는다. 그리고 찾은 육지 위치에 대해 dfs를 실행한다. 

dfs 함수는 재귀적으로 실행되어야 하므로 solution 함수 안의 또 다른 함수(내부 함수)로 선언한다. 

내부 함수로 선언된 dfs() 함수는 solution 함수에서 선언된 지역 변수들의 값을 가져오거나 변경할 수 있어서 재귀 방식을 사용할 때 많이 사용된다. 

dfs 함수에서는 우선 해당 위치가 유효한지(해당 위치가 물인지, 가로와 세로가 grid의 범위에서 벗어나지 않았는지)를 확인한 다음에 그 위치의 값을 육지에서 물로 바꾼다(1->0). 그리고 그 위치를 기준으로 동서남북으로 dfs 탐색을 진행하면서 사방의 육지를 물로 바꾼다.

만약 육지가 여러 개가 아니고 하나였다면 for loop에서 한 번의 dfs() 호출로 모든 육지가 물로 바뀔 것이다. 이 경우 값은 1이다. 

또는 만약 육지가 아예 없었다면 for loop에서 육지를 찾을 수 없으므로 count가 증가하지 않아서 육지의 개수는 0이 될 것이다. 

다음 그림은 leetcode의 예제 1번을 그림으로 표현한 것이다. 검정색 점은 육지이고 파란색 점은 물이다. 

for loop로 육지를 탐색한다면 grid[0][0]인 맨 위의 점에 대해서 맨 먼저 dfs() 함수가 호출될 것이다. 

dfs()가 호출된 경우 해당 위치가 유효한지를 먼저 판단한 뒤, 유효하면 해당 위치의 값을 육지에서 물로 바꾼다.

교재에서 제시한 dfs() 함수에서는 남->북->동->서 방식으로 탐색을 진행하므로, 그 다음엔 한 칸 아래에 있는 점에 대해서 dfs()를 다시 호출한다. 

dfs()가 계속 호출되면서 아래 그림처럼 모든 점이 육지에서 물로 바뀐다. 

해당 예시에서는 육지가 1개였으므로 모든 점이 물이 되지만, 육지가 여러 개일 경우 검정 점이 남아있다. 

현재는 (4, 2)에서 dfs()가 동작하지만 이제 사방의 모든 점이 물이므로 dfs()를 더 이상 호출하지 않고 해당 점을 기준으로 호출된 dfs()는 종료될 것이다. 

그러면 해당 점을 호출하기 전의 위치인 (4, 1)에서 다시 남은 dfs() 코드가 실행될 것이다.

하지만 사방의 모든 점이 물이므로 해당 점에서의 dfs()는 종료될 것이며, (4, 1)을 기준으로 dfs()를 호출한 이전 위치의 dfs() 실행 지점으로 돌아갈 것이다. 

이렇게 맨 처음 dfs()를 호출한 (1, 1)에서도 dfs()가 종료되면 (0, 0)이 속한 육지를 물로 바뀌었으니 육지 count가 1 증가한다. 

그리고 for loop가 다시 실행되어 남은 점들에 대해서 육지가 있는지 탐색할 것이다. 하지만 남은 육지가 없으므로 1을 리턴하게 된다. 

* 해당 포스트는 <파이썬 알고리즘 인터뷰> 공부 후 정리 목적으로 작성되었습니다. *

leetcode 347번 ( https://leetcode.com/problems/top-k-frequent-elements/ )

풀이 1. 

collections 라이브러리의 Counter 자료형에서 기본으로 주어지는 메소드만으로도 풀 수 있다. 

Counter 객체를 초기화할 때 매개변수로 문자열이나 리스트를 넣을 수 있다. Counter 클래스는 딕셔너리의 하위 클래스라서 딕셔너리의 기본 기능들은 다 가지고 있다. 다만 문자열의 문자나 리스트의 개별 원소를 key 값으로, 해당 문자나 원소의 등장 빈도를 value로 갖는다. 

counter = collections.Counter(nums)	# initialize Counter object

Counter 클래스의 most_common(k) 메소드를 사용하면 Counter에 저장된 key-value pair 중 가장 등장빈도(value)가 높은 쌍을 총 k개 리턴한다. 

리스트 형태로 리턴하고, 리스트의 각 원소는 (key, value)로 된 튜플(tuple) 형식이다. 

return counter.most_common(k)
# [(1,4), (2,3)] (when 1 appeared 4 and 2 appeared 3 times)

list comprehension을 통해서 이 튜플-리스트를 key만 들어있는 리스트 형태로 바꿔 주면 된다. 

(key는 튜플의 0번째 인덱스이다.)

전체 코드는 다음과 같다. 

class Solution(object):
	def topKFrequent(self, nums, k):
		counter = collections.Counter(nums)
		return [mc[0] for mc in counter.most_common(k)]

풀이 2. 

풀이 1번에서 맨 마지막에 for loop로 리스트 컴프리헨션을 사용하지 않고, zip()을 사용해서 더 간단히 풀 수 있다고 한다. 

zip() 함수는 여러 개의 리스트를 병렬적으로 묶어 준다. 

nums = [1,2,3]
alphabets = ["a","b","c"]

for z in zip(nums, alphabets):
	print(z)
    
# [1, "a"]
# [2, "b"]
# [3, "c"]

풀이 1번의 코드를 이렇게 바꿀 수 있다. 

class Solution(object):

    def topKFrequent(self, nums, k):    
        counter = collections.Counter(nums)
        return list(zip(counter.most_common(k))[0])

풀이 3. 

Counter 변수는 리스트의 값과 발생빈도를 저장하는 용도로만 사용하고, 힙에다가 Counter에 있는 값들을 저장 및 정렬해서 하나씩 총 k개를 빼는 방법도 있다. 힙을 사용할 때는 priority-queue와 heapq 라이브러리 등 여러 라이브러리가 있지만 thread-safe로 인한 locking 오버헤드 문제 때문에 여기서는 heapq 라이브러리를 사용한다. 

힙에 counter의 원소들(key-value 한 쌍)을 넣을 때는 heappush() 메소드를 사용한다. 

heapq.heappush(heap 변수, heap 변수에 넣을 값)

값을 넣을 때는 counter 객체에서 자동으로 계산해 준 등장 빈도(value)를 음수로 바꿔서 넣는다. heapq는 min heap만 제공하기 때문이다. 

(정확히는 max heap도 제공하지만 해당 메소드는 protected 메소드라서 직접 접근하는 것은 권장하지 않는다.)

힙에 저장된 원소들을 제거할 때는 heappop() 메소드를 사용한다. 매개변수를 받지 않으며, heap에 저장된 값을 정렬한 뒤 가장 작은 원소부터 리턴한다. 

heapq.heappop()

이후 heappop()으로 힙에서 정렬된 원소들을 총 k번 빼 주고, heappop()을 통해 힙에서 제거되어 반환된 key-value 쌍은 리스트에 저장해 주자. 

참고한 포스트

https://docs.python.org/3/library/collections.html

* 해당 포스트는 <파이썬 알고리즘 인터뷰> 공부 후 정리 목적으로 작성되었습니다. *

leetcode 3번 ( https://leetcode.com/problems/longest-substring-without-repeating-characters/ )

풀이 1. 

시간 복잡도의 제한이 없다면 for loop를 2번 사용하면 간단히 풀 수 있다. 

start의 값을 정한 뒤 해당 위치보다 뒤에 있는 문자열들을 전부 돌면서 이전에 나왔던 문자열과 겹치지 않으면 count를 1씩 증가시키고, 겹친다면 for loop에서 탈출한다. 따라서 총 시간 복잡도는 O(n^2)이다. 

전체 풀이는 다음과 같다. 

class Solution(object):

    def lengthOfLongestSubstring(self, s):
    
        maxCount = 0
        for i in range(len(s)):
            strs = ""
            for string in s[i:]:
                if string not in strs:
                    strs += string
                else:
                    break
            maxCount = maxCount if maxCount > len(strs) else len(strs)

        return maxCount

풀이 2. 

교재에서는 더 간단히 풀 수 있는 방법을 제시한다. 바로 for loop를 두 번 도는 대신 투 포인터를 이용해서 for loop를 한 번만 도는 것이다. 

이전에 나왔던 문자열인지를 확인하는 작업이 필요한데 여기서는 딕셔너리 변수를 해시맵으로 사용해서 이전에 나온 문자열인지를 확인한다. 

포인터 하나(index, string)는 전체 문자열을 돌면서 해당 문자열이 해시맵(used)에 포함되어 있는지를 체크한다. index는 현재 탐색하는 문자열의 위치를, string은 현재 탐색하는 문자열 자체를 값으로 갖는다. 

나머지 포인터 하나(start)는 문자열이 시작하는 기준점을 가리킨다. 

또한 maxCount 변수도 선언해서 최대값을 계속 업데이트 할 수 있도록 한다. 

maxCount = max(maxCount, other_value)

해시맵 used는 문자열을 key로, 해당 문자열의 위치를 value로 갖는다. 문자열을 순회하다가 이전에 있던 문자열이 다시 등장하면 값을 수정한다. 

used[string] = index

예를 들어서 'a'라는 문자가 1번째 인덱스(앞에서 두 번째)에 있는 경우는 다음과 같다. 

만약 index 포인터가 가리키는 문자열(string)의 값이 이미 used에 포함되어 있고, 문자열의 위치 값도 start 포인터 값보다 크다면 해당 문자열은 중복된 문자열이다. 

예를 들어서 "abcabcbb" 를 탐색한다고 가정하자. 

현재 start(문자열이 시작하는 기준점) 값은 2라고 두면, 'c'부터 문자열이 시작한다고 보면 된다.

그리고 index(순회하는 문자열의 기준점) 값은 5라고 두자. 그러면 index는 두 번째 'c'를 가리키고 있다. 이때 해당 문자열의 위치 값은 5로, start 포인터 값인 2보다 크다. 즉 첫 번째 c를 시작점으로 두고 탐색하고 있는데 두 번째 c가 나온 것이므로 중복 문자열이 나온 것이다. 

그럴 땐 start 포인터의 값을 현재 탐색하고 있는 문자열의 위치 + 1로 바꿔 준다. 

start = used[string] + 1

만약 아니라면 count 변수의 값을 비교해서 1 증가시킨다. 

4번째 경우도 마찬가지로, 첫 번째 'a'에서부터 탐색을 하고 있는데 두 번째 'a'가 등장했으므로 중복 문자열이 나타난 상황이다. 이 경우 used[a]의 값도 새로 변경되고, 0이었던 start 값도 3으로 바꿔 준다. 

* 해당 포스트는 <파이썬 알고리즘 인터뷰> 공부 후 정리 목적으로 작성되었습니다. *

leetcode 771번 ( https://leetcode.com/problems/jewels-and-stones/ )

풀이 1 : Counter

(교재를 참고하지 않은 풀이입니다.)

해시맵 단원의 문제인만큼 해시맵을 사용해서 풀 수 있다. 

파이썬의 딕셔너리 자료형은 내부적으로 해시맵으로 구현되어 있다. 또한 파이썬에는 딕셔너리를 상속받은, 즉 딕셔너리의 하위 클래스인 다른 클래스들도 있는데, 이 클래스들은 (key, value) 한 쌍을 저장하는 딕셔너리의 기본 특징에 더해서 추가적인 기능이 있다.

딕셔너리의 하위 클래스로는 Counter가 대표적이다. 

Counter는 초기화할 때 리스트나 문자열을 매개변수로 받을 수 있다. 이 경우 리스트나 문자열에 포함된 원소가 key, 해당 원소가 몇 번 나타났는지가 value가 된다. 그래서 문자열의 등장 빈도를 알고 싶다면 Counter으로 간단하게 계산할 수 있다. 

우선 stones 문자열을 매개변수로 사용해서 Counter 객체를 만들어 준다. 그러면 그 Counter 객체는 stones의 각 문자열을 key 값으로, 해당 문자열의 등장 빈도(숫자)를 value로 갖는다. 

또한 없는 문자열을 조회하려고 한다면 오류를 발생시키지 않고 0을 리턴한다. 

그리고 jewels에 대해 for loop를 돌려서, 각 jewels 알파벳의 value 값(=등장 빈도)를 모두 더한 뒤 리턴한다. 

전체 코드는 다음과 같다. 

class Solution(object):

    def numJewelsInStones(self, jewels, stones):
    
        counter = collections.Counter(stones)
        count = 0
        for j in jewels:
            count += counter[j]
        return count

풀이 2: 리스트 컴프리헨션(List Comprehension)

교재에서는 이 코드를 한 줄로 정리하는 방법도 제시한다. 

list comprehension을 이용하면 짧은 코드로 기존 리스트(jewels, stones)의 값을 이용해서 새 리스트들 만들 수 있다. 

def solution(self, jewels, stones):
	return sum(s in jewels for s in stones)

* 해당 포스트는 <파이썬 알고리즘 인터뷰> 공부 후 정리 목적으로 작성되었습니다. *

leetcode 706번 ( https://leetcode.com/problems/design-hashmap/ )

풀이 1. 

(leetcode에서 정답 처리되었으나 hash collision이 발생하는 경우를 처리하는 로직이 없어서 수정이 필요한 풀이입니다. 풀이 2에서 hash collision 처리 로직을 포함하였습니다.)

문제에서는 해시맵(hashmap)의 크기나, hash collision이 발생했을 때 어떤 방식으로 대처할지 등을 제시하지 않았다. 그러므로 임의로 크기를 할당하면 된다. 

put()으로 해시맵에 (key, value) entry를 넣으려면 해시 함수(hash function)를 만들어야 한다.

해시맵의 key, value는 모두 정수형이므로 가장 간단한 방식으로는 key값 mod hashmap size를 해시 함수로 둘 수 있다. 

def put(self, key, value):
        index = key % self.size		# hash function
        self.hashMap[index] = value

전체 코드는 다음과 같다. 

class MyHashMap(object):

    def __init__(self):
        self.size = 10 ** 6
        self.hashMap = [None] * self.size

    def put(self, key, value):
        index = key % self.size
        self.hashMap[index] = value
        

    def get(self, key):
        index = key % self.size
        if self.hashMap[index] is None:
            return -1
        return self.hashMap[index]
        

    def remove(self, key):
        index = key % self.size
        if self.hashMap[index] is not None:
            self.hashMap[index] = None

풀이 2. 

위의 풀이는 hashmap을 일반 리스트로 구현하였다. 하지만 collections 라이브러리를 사용해서 딕셔너리로 구현한다면 해시맵에 없는 키를 조회했을 때 오류가 나지 않고 자동으로 새 값을 만들  수 있다. 

self.hashMap = collections.defaultdict()

위의 풀이도 정답으로 처리되지만 hash collision이 일어날 경우를 처리하지 않는다. 

예를 들면 size=10인 해시맵에 (7, 20), (17, 30) 두 개의 entry를 put()으로 넣는다고 해 보자. 

hash collision을 처리하지 않은 위의 경우는 key=7을 get()으로 조회하였을 때 20이 아닌 30을 리턴한다. 

7 mod 10 = 7, 17 mod 10 = 7로 key 깂이 같아서 hashmap[7]의 값이 20에서 30으로 대체되었기 때문이다. 

만약 hash collision을 개별 체이닝(separate chaining) 방식으로 처리한다고 가정한다면 hashmap[7]을 조회하면 20, hashmap[17]을 조회하면 30이 나온다. 교재를 참고해서 수정해 보자. 

open addressing

교재에서도 separate chaining 방법을 사용해서 hash collision에 대처하고 있다. 개별 체이닝 방법 말고도 오픈 어드레싱(open addressing) 방법이 있다. 하지만 이 방법은 hash collision이 발생할 경우 선형 탐색(linear probing)이나 다른 해시 함수를 추가로 사용해야 하며 clustering(같은 bucket(인덱스) 값을 가진 entry들이 서로 뭉쳐서 분포하는 현상) 등의 문제가 있기 때문에 사용하지 않은 것으로 보인다. 

separate chaining

separate chaining은 hash collision이 발생했을 때 하나의 bucket을 연결 리스트로 연결해서 bucket 값은 같고 key 값은 다른 entry들을 계속 연결한다. 이 방법은 open addressing처럼 hash collision을 발생시킨 entry를 어느 자리에 추가로 배치할지를 고려하지 않아도 된다는 장점이 있다. 반면 해시 함수가 들어오는 entry들을 고르게 분포시키지 못할 경우 탐색 시간이 최대 O(n)만큼 걸릴 수 있다는 단점도 있다. 

separate chaining을 사용하려면 개별 entry가 들어올 때마다 노드를 생성해야 한다. 그래야 포인터를 통해 연결 리스트를 탐색할 수 있다. 

연결 리스트의 경우 보통은 단일 연결 리스트(singly linked list)로 구현한다. 

class ListNode(object):

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

* 해당 포스트는 <파이썬 알고리즘 인터뷰> 공부 후 정리 목적으로 작성되었습니다. *

leetcode 23번 ( https://leetcode.com/problems/merge-k-sorted-lists/ )

풀이

교재의 방법처럼 우선순위 큐(priority queue)를 사용하면 쉽게 풀 수 있는 문제다. 

기존의 큐는 먼저 추가된 원소를 먼저 반환하는 FIFO 구조였다면, 우선순위 큐는 큐 안의 원소를 특정한 우선순위에 따라서 정렬한 뒤 우선순위가 가장 높은 원소를 반환한다. 

priority queue vs heapq

파이썬에서도 우선순위 큐를 지원하는 모듈이 있다. 그러나 교재에서는 heapq 모듈을 사용해서 진행했다.

실제로 우선순위 큐를 구현할 때는 힙(heap)을 주로 사용하고, 파이썬의 우선순위 큐 구현 코드를 보면 heapq 모듈을 사용하고 있다고 하므로 기능의 차이는 없다. 

다만 priority queue 모듈은 thread-safe인 반면 heapq는 thread-safe가 아니다. thread-safe란 멀티 스레드 환경에서 각 스레드에서 사용하는 변수의 값이 다른 스레드에 의해 변경되지 않는 것을 의미한다. 

그럼 thread-safe를 지원하는 priority queue가 더 좋은 것이 아니야? 라고 생각할 수 있지만, thread-safe를 지원하기 위해서는 내부적으로 락킹(locking)을 지원해야 한다. 추가적인 기능을 제공하기 위해서 오버헤드가 발생할 수 있고, 코딩 테스트는 멀티 스레드(multi-thread) 환경에서 실행하지 않으므로 priority queue 모듈을 사용할 필요가 없는 것이다. 

Locking이란, 멀티 스레드 환경에서 여러 개의 스레드가 동시에 한 변수에 접근하는 것을 막는 것이다. 그래야만 한 스레드가 어떤 변수를 사용 중일 때 다른 스레드의 개입으로 해당 변수의 값이 바뀌지 않는다. 

heap

힙은 또 다른 자료형(ADT)이며 리스트나 연결 리스트 등 다양한 자료형으로 구현할 수 있지만 보통은 리스트로 구현하는 듯 하다. 

힙은 min heap과 max heap이 있고, min heap의 경우 부모 노드(parent)는 자식 노드(children)보다 작거나 같은 key 값을 갖는 게 특징이며, 이를 heap property라고 한다. 그 외에는 다른 자료구조처럼 노드를 추가나 삭제하는 것은 똑같다. 노드를 하나 삭제나 추가할 때마다 heap property를 위반하지 않도록 필요 시 부모 노드와 자식 노드의 값을 바꾸는 등의 정렬 작업을 한다. 

알고리즘

어쨋든 풀이에서는 힙 자료형을 사용하면 문제를 쉽게 풀 수 있다고 한다. 어떻게 가능할까?

힙에 heappush()로 여러 값을 넣으면 자동으로 정렬을 해 준다. 이후 heappop()로 가장 우선순위가 낮은(여기서는 값이 작은) 원소를 리턴할 수 있다. 

for i in range(len(lists)):
	heapq.heappush(lists[i].val)

다만 힙에서는 값이 연결 리스트의 노드 형식이 아니라 숫자 형식으로 되어 있으므로 연결 리스트 형식으로 바꿔주는 작업도 필요하다. 

새 연결 리스트 노드를 만든 뒤 next 포인터로 새로 만든 노드(ListNode(value))를 가리키게 하고, 포인터를 뒤로 한 칸씩 이동하면 된다. 

heap: key 중복

다만 heapq 라이브러리에서 구현한 힙은 중복 key 값을 허용하지 않는다. 문제의 예제에서는 값이 '1'로 중복되는 경우가 있어서 오류가 발생한다. 

이 경우 값을 가공하지 않은 채 숫자 형태로 넣지 말고, tuple 형태로 가공해서 0번째 인덱스에는 노드의 값을 넣고, 1번째 인덱스에는 해당 노드가 속한 연결 리스트가 input lists 중 몇 번째 인덱스인지를 입력해 주자. 그렇게 하면 설령 0번째 인덱스인 노드의 값이 서로 겹치더라도 그 다음 1번째 인덱스로 값을 구분해서 중복 오류가 나지 않는다. 물론 실제로 1번째 인덱스 값은 사용하지 않지만 말이다. 

heap: node.next

아까 for loop를 돌면서 lists의 i번째 인덱스를 넣었었다. 그런데 lists[i].val은 연결 리스트에 있는 모든 노드의 값이 아니라 연결 리스트의 첫 번째 노드의 값이다. 그래서 이 상태는 아직 그 다음 노드들의 값이 정렬되지 않은 상태이다. 

우선 각 연결 리스트의 첫 번째 노드들만 힙에 넣고, heappop()으로 가장 값이 작은 노드 하나를 리턴한다. 그리고 연결 리스트의 다음 노드를 다시 힙에 넣는다. 

맨 처음이 이런 상황이다. 현재 a 연결 리스트를 대상으로 정렬 작업을 하고 있다고 가정하면, 그 다음 상태는 이렇게 된다. 

이 방법이 가능한 이유는 각 연결 리스트(a, b, c)는 정렬이 된 상황이기 때문이다. 만약 그렇지 않았다면 모든 연결리스트의 모든 노드를 힙에 넣은 뒤 정렬을 해야 했을 것이다. 

참고한 포스트

https://docs.python.org/3/library/heapq.html

https://github.com/python/cpython/blob/main/Lib/heapq.py