문제
Design a data structure to store the strings' count with the ability to return the strings with minimum and maximum counts.
Implement the AllOne class:
AllOne() Initializes the object of the data structure.
inc(String key) Increments the count of the string key by 1. If key does not exist in the data structure, insert it with count 1.
dec(String key) Decrements the count of the string key by 1. If the count of key is 0 after the decrement, remove it from the data structure. It is guaranteed that key exists in the data structure before the decrement.
getMaxKey() Returns one of the keys with the maximal count. If no element exists, return an empty string "".
getMinKey() Returns one of the keys with the minimum count. If no element exists, return an empty string "".
Note that each function must run in O(1) average time complexity.문자열별 등장 횟수를 저장하면서, 등장 횟수가 가장 적은 문자열과 가장 많은 문자열을 반환할 수 있는 자료구조를 설계하세요.
AllOne 클래스를 구현하세요.
-
AllOne()
자료구조를 초기화합니다. -
inc(String key)
문자열key의 개수를 1 증가시킵니다.
key가 자료구조에 존재하지 않는다면, 개수가 1인 상태로 새로 추가합니다. -
dec(String key)
문자열key의 개수를 1 감소시킵니다.
감소한 결과 개수가 0이 되면 해당 문자열을 자료구조에서 제거합니다.
dec가 호출되기 전에는key가 반드시 자료구조에 존재함이 보장됩니다. -
getMaxKey()
개수가 가장 큰 문자열 중 하나를 반환합니다.
자료구조가 비어 있다면 빈 문자열""을 반환합니다. -
getMinKey()
개수가 가장 작은 문자열 중 하나를 반환합니다.
자료구조가 비어 있다면 빈 문자열""을 반환합니다.
모든 함수는 평균적으로 O(1)의 시간 복잡도로 동작해야 합니다.
예시
입력
["AllOne", "inc", "inc", "getMaxKey", "getMinKey", "inc", "getMaxKey", "getMinKey"]
[[], ["hello"], ["hello"], [], [], ["leet"], [], []]출력
[null, null, null, "hello", "hello", null, "hello", "leet"]설명
AllOne allOne = new AllOne();
allOne.inc("hello");
// "hello"의 개수를 1로 설정합니다.
allOne.inc("hello");
// "hello"의 개수가 2가 됩니다.
allOne.getMaxKey();
// 현재 개수가 가장 큰 키인 "hello"를 반환합니다.
allOne.getMinKey();
// 현재 존재하는 키가 "hello"뿐이므로 "hello"를 반환합니다.
allOne.inc("leet");
// "leet"를 개수 1로 추가합니다.
allOne.getMaxKey();
// "hello"의 개수는 2, "leet"의 개수는 1이므로 "hello"를 반환합니다.
allOne.getMinKey();
// 개수가 가장 작은 키인 "leet"를 반환합니다.제한
- 키는 영어 소문자로만 구성된다.
- 각 메소드는 최대 번 호출된다.
풀이
이 문제는 카운트를 기준으로 정렬된 이중 연결 리스트를 구성하는 방식으로 해결할 수 있다.
각 노드는 하나의 카운트를 나타내며, 해당 카운트를 가진 모든 문자열을 하나의 set에 저장한다. 예를 들어 카운트가 2인 문자열이 여러 개라면, 각각 별도의 노드를 만드는 것이 아니라 카운트 2를 나타내는 하나의 노드에 모두 보관한다.
연결 리스트는 Head에 가까울수록 작은 카운트가, Tail에 가까울수록 큰 카운트가 위치하도록 유지한다. 따라서 최솟값은 head.next, 최댓값은 tail.prev에서 바로 확인할 수 있다.
문자열의 카운트를 증가시키거나 감소시킬 때는 현재 노드의 바로 앞이나 뒤에 있는 노드로 문자열을 이동시킨다. 이동할 카운트에 해당하는 노드가 없다면 새 노드를 만들어 현재 노드의 인접한 위치에 삽입한다.
문자열이 이동한 뒤 기존 노드에 남아 있는 문자열이 없다면 해당 노드는 연결 리스트와 저장소에서 제거한다.
또한 다음 두 개의 해시맵을 함께 사용한다.
storage: 카운트별 노드를 저장한다.key_to_count: 각 문자열의 현재 카운트를 저장한다.
이를 통해 문자열의 현재 위치와 이동할 노드를 평균 O(1)에 찾을 수 있다. 연결 리스트의 삽입과 삭제 역시 O(1)이므로, 모든 메소드를 평균 O(1)의 시간 복잡도로 구현할 수 있다.
from typing import Set
class Node:
def __init__(self):
self.keys: Set[str] = set()
self.prev: Node = None
self.next: Node = None
def __repr__(self):
return str(self.keys)
class AllOne:
def __init__(self):
self.head = Node()
self.tail = Node()
self.head.next = self.tail
self.tail.prev = self.head
self.storage: Dict[int, Node] = dict()
self.key_to_count: Dict[str, int] = dict()
def __repr__(self):
node = self.head.next
values = []
while node is not self.tail:
values.append(f'[{node}]')
node = node.next
return ' -> '.join(values)
def _place_head(self, node: Node):
prev_head = self.head.next
self.head.next = node
node.prev = self.head
node.next = prev_head
prev_head.prev = node
def _remove(self, node: Node):
prev_node = node.prev
next_node = node.next
prev_node.next = next_node
next_node.prev = prev_node
def _place_next(self, node: Node, target: Node):
current_next = node.next
node.next = target
target.prev = node
target.next = current_next
current_next.prev = target
def _place_prev(self, node: Node, target: Node):
current_prev = node.prev
node.prev = target
target.next = node
current_prev.next = target
target.prev = current_prev
def inc(self, key: str) -> None:
# 값이 1인게 없으면
if key not in self.key_to_count:
# 1인 값들의 키 노드 만들고 배치
if 1 not in self.storage:
one_node = Node()
self.storage[1] = one_node
self._place_head(one_node)
# 1인 값들의 노드에 키 추가하기
self.storage[1].keys.add(key)
self.key_to_count[key] = 1
return
# 타겟 노드 위치 찾기
current_freq = self.key_to_count[key]
current_node = self.storage[current_freq]
# 다음 노드 자리 없으면 일단 만들기
if current_freq + 1 not in self.storage:
node = Node()
self.storage[current_freq + 1] = node
self._place_next(current_node, node)
# 노드 위치 옮기기
self.storage[current_freq].keys.remove(key)
self.storage[current_freq + 1].keys.add(key)
self.key_to_count[key] += 1
# 노드가 비어있게 되면 삭제하기
if len(self.storage[current_freq].keys) == 0:
self._remove(self.storage[current_freq])
del self.storage[current_freq]
def dec(self, key: str) -> None:
current_freq = self.key_to_count[key]
current_node = self.storage[current_freq]
# 원래 빈도에서 키 삭제
current_node.keys.remove(key)
# 줄어들면 0이 될 경우
if current_freq - 1 == 0:
del self.key_to_count[key]
# 아닌데 자리가 없는 경우
elif current_freq - 1 not in self.storage:
node = Node()
node.keys.add(key)
self.storage[current_freq - 1] = node
self._place_prev(current_node, node)
self.key_to_count[key] -= 1
# 아니고 자리가 있는 경우
else:
self.storage[current_freq - 1].keys.add(key)
self.key_to_count[key] -= 1
# 옮긴 원래 자리가 비는 경우 삭제하기
if len(self.storage[current_freq].keys) == 0:
self._remove(current_node)
del self.storage[current_freq]
def getMaxKey(self) -> str:
if self.tail.prev is self.head:
return ""
return next(iter(self.tail.prev.keys))
def getMinKey(self) -> str:
if self.head.next is self.tail:
return ""
return next(iter(self.head.next.keys))
만능 컴덕후 겸 번지 팬