https://leetcode.com/problems/design-hashmap/
해쉬맵 디자인
'''
Design a HashMap without using any built-in hash table libraries.
Implement the MyHashMap class:
MyHashMap() initializes the object with an empty map.
void put(int key, int value) inserts a (key, value) pair into the HashMap. If the key already exists in the map, update the corresponding value.
int get(int key) returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key.
void remove(key) removes the key and its corresponding value if the map contains the mapping for the key.
void put(int key, int value): 해쉬 맵에 Key, value 페어를 넣어라
만약 키가 이미 존재하면 값을 업데이트하라
int get(int key)키에 매핑된 값을 리턴하라, 만약 키에 연결되는 매핑이 없으면 -1을 리턴
void remove(key) 키와 값을 제거하라
오늘은 시간이 없어서 먼저 책을 읽음
'''
import collections
'''
'''
class ListNode:
def __init__(self, key=None, value=None):
self.key = key
self.value = value
self.next = None
class MyHashMap:
# 초기화
def __init__(self):
# size 1000으로 정하고, 삽입시 모듈러(나머지) 연산에서 사용함
# 즉 5와 1005는 같은 해쉬에 들어가며 연결리스트로 정리 됨
self.size = 1000
self.table = collections.defaultdict(ListNode)
# 삽입
def put(self, key: int, value: int) -> None:
# 문제는 편의상 모든 키를 정수형으로 지정
# size 개수만큼 나머지 연산을 한 나머지를 해시값으로 정함
index = key % self.size
# 인덱스에 노드가 없다면 삽입 후 종료
# defaultdict는 참조시 비어있는 인덱스는 자동으로 key를 생성하기에 value를 비교 대상으로 삼음
if self.table[index].value is None:
self.table[index] = ListNode(key, value)
return
# 인덱스에 노드가 존재하는 경우 연결 리스트 처리
p = self.table[index]
while p:
if p.key == key:
p.value = value
return
if p.next is None:
break
p = p.next
p.next = ListNode(key, value)
# 조회
def get(self, key: int) -> int:
index = key % self.size
if self.table[index].value is None:
return -1
# 노드가 존재할 때 일치하는 키 탐색
p = self.table[index]
while p:
if p.key == key:
return p.value
p = p.next
return -1
def remove(self, key: int) -> None:
index = key % self.size
if self.table[index].value is None:
return
# 인덱스의 첫 번째 노드일 때 삭제 처리
p = self.table[index]
if p.key == key:
self.table[index] = ListNode() if p.next is None else p.next
return
# 연결 리스트 노드 삭제
prev = p
while p:
if p.key == key:
prev.next = p.next
return
prev, p = p, p.next
https://leetcode.com/problems/jewels-and-stones
보석과 돌
'''
J는 보석이며, S는 갖고 있는 돌이다.
S에는 보석이 몇 개나 있을 까? 대소문자는 구문 한다.
You're given strings jewels representing the types of stones that are jewels,
and stones representing the stones you have.
Each character in stones is a type of stone you have.
You want to know how many of the stones you have are also jewels.
Letters are case sensitive, so "a" is considered a different type of stone from "A".
입력
J = "aA", s = "aAAbbbb"
출력
3
일단 도는 대상은 S
S의 개별 값이 J라는 해시테이블에 존재하는 경우 값을 올려 주면 될 듯 함
'''
import collections
class Solution:
'''
개인 답안
다행이 쉬운 문제였는지 정답이 맞았음
처음에 존재 여부를 확인하려고 직접 index에 접근해서 is None을 판별하는데, 오류가 발생함
없는 index를 참조해서 그런가 생각해 collections.defaultdict 사용 했지만 동일 했음
대신 그냥 if in으로 구분을 해버림
오히려 조금 더 편해진 느낌임
'''
def numJewelsInStonesMyway(self, jewels: str, stones: str) -> int:
table = {}
count = 0
for jewel in jewels:
table[jewel] = 1
for stone in stones:
if stone in table:
count += 1
return count
'''
답안 1: 해시 테이블을 이용한 풀이
나와는 관점이 반대임, 난 보석을 key로 활용 했지만
답안에서는 돌을 답안으로 활용 함
아예 돌을 먼저 계산을 해서 개수를 따로 정리
이후 보석을 돌에 매칭시키면서 해당 돌에 개수를 받아 합쳐서 리턴
'''
def numJewelsInStones(self, J: str, S: str) -> int:
freqs = {}
count = 0
# 돌(S)의 빈도 수 계산
for char in S:
if char not in freqs:
freqs[char] = 1
else:
freqs[char] += 1
# 보석(J)의 빈도 수 합산
for char in J:
if char in freqs:
count += freqs[char]
return count
'''
답안2: defaultdict를 이용한 비교 생략
값이 없는 경우 기본값을 넣기 때문에 있는지 여부를 확인할 필요가 없음
코드가 매우 깔끔함
'''
def numJewelsInStonesDefaultdict(self, J: str, S: str) -> int:
freqs = collections.defaultdict(int)
count = 0
# 비교 없이 돌(S) 빈도 수 계산
for char in S:
freqs[char] += 1
# 비교 없이 보석(J) 빈도 수 합산
for char in J:
count += freqs[char]
return count
'''
답안3: Counter로 계산 생략
점점 짧아지는게 놀랍기도 함
생각해보니 전에 counter 본적이 있는데 왜 생각 안났는지 모르겠음
생각 했으면 이 답안은 내께 됬을 텐데
'''
def numJewelsInStonesCounter(self, J: str, S: str) -> int:
freqs = collections.Counter(S) # 돌(S) 빈도 수 계산
count = 0
# 비교 없이 보석(J) 빈도 수 합산)
for char in J:
count += freqs[char]
return count
'''
답안4: 파이썬 다운 방식
점점 줄어드는 꼴을 바라보고 있으니 돌아버릴 꺼 같음
s for s in S는
['a', 'A', 'A', 'b', 'b', 'b', 'b']
s in J for s in S는
[True, True, True, False, False, False, False]
즉 S의 문자 s가 J에 포함되어있는지 여부를 출력
첫번째 in은 if, 두번째 in은 for 방식임
True는 숫자로 1로 취급되니 sum으로 합산
'''
def numJewelsInStonesPython(self, J: str, S: str) -> int:
return sum(s in J for s in S)https://leetcode.com/problems/longest-substring-without-repeating-characters/
중복 문자 없는 가장 긴 부분 문자열
'''
중복 문자가 없는 가장 긴 부분 문자열(substring)의 길이를 리턴하라
입출력 예제 1:
입력
"abcabcbb"
출력
3
설명
정답은 "abc"로 길이는 3
입출력 예제 2:
입력
"bbbbb"
출력
1
설명
정답은 "b" 길이는 1
입출력 예제 3:
입력
"pwwkew"
출력
3
설명
정답은 "wke" 길이는 3
초기 생각
부분 문자열이니 당연하겠지만 다 리턴하고 중복이 아닙니다 이런짓은 못하겠음
생각나는건 for문 중첩 또는 재귀함수
다 돌면서 각자 중첩이 되지않을 때 까지의 길이를 다 계산하고
Max로 최고를 내는 것
다만 연산이 제곱이라....고민이 됨
한번에 여기에서 처리를 하려면 반복문이 적게 돌아야함
재귀를 돌린다고 할때,
"abcabc"에 경우
a를 검증하다가 a를 만나면 멈춤
a는 넘어가고 b의 시작
bca 검증하고 b를 만나면 멈춤...
일단 고려된 앞에 요소는 더이상 고려안함
하지만 그 길이값은 따로 보관이 필요함
이 문제가 해시테이블인 이유가 있음
일단 각 요소(시작 부분)부터 중복전 요소까지의 길이를 저장해야함
{1: 3, 2: 3}과 같이 각 포인트 별로 길이를 저장
일단 for문이 2개면 충분 할 것 같으니 진행
'''
import collections
class Solution:
'''
생각해보니 for 이후 2번째 for때 자기자신과 지나온 요소는 고려할 필요가 없음
for문이 아닌 while문으로 변경
end로 나가면서 자기 자신과 똑같은 수만 고려했지만,
생각해보니 지나온 다른 요소들도 곂치는지 계산이 필요함...
즉 "abc"에서 a가 아니라 b랑 c도 같이 계산이 필요
문제가 해시인 이유가 있었음
반복시마다 지금까지 같이온 문자를 key로 해시 테이블에 넣고,위치를 value로 넣는 방안 고려
새로운 요소를 검사시 해당 요소가 start랑 일치하면 분기 종료
아니면 테이블에 있는지 검사해 있으면 start 위치 변경
루틴을 고민하다가 결국 포기
발표준비할 시간이 필요해서 이건 답안을 보고 경험을 삼기로 함
'''
'''
답안: 슬라이딩 윈도우와 투 포인터로 사이즈 조절
일단 근처까지는 간거 같음
하지만 루틴을 돌면서 길이를 전부 구해 해시로 삼을려고 했던 관점이 다름
결과에 표시될 길이는 숫자가 중요하지 누구껀가 그게 중요한건 아니었음
max로 그냥 값을 간단하게 끌고 다님
또한 해시를 사용되었던 글자의 목록으로 잘 활용함 이점을 배워야겠음음
'''
def lngthOfLongestSubstring(self, s: str) -> int:
used = {}
max_length = start = 0
for index, char in enumerate(s):
# 이미 등장했던 문자라면 'start' 위치 갱신
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
https://leetcode.com/problems/top-k-frequent-elements/
상위 K 빈도 요소
'''
상위 k번 이상 등장하는 요소를 추출하라
Given an integer array nums and an integer k,
return the k most frequent elements.
You may return the answer in any order.
입력
nums = [1,1,1,2,2,3], k =2
출력
[1,2]
조건
1 <= nums.length <= 105
k is in the range [1, the number of unique elements in the array].
It is guaranteed that the answer is unique.
초기 생각
여러 요소들을 정리해서 몇번 등장하도록 나오게 하는 것은 Counter를 쓰면 될 듯 함
Counter를 쓰면 매우 쉬워질 것 같지만...저번에도 썻으니 괜찮을 듯 함
'''
import collections
import heapq
from typing import List
class Solution:
'''
개인답안
는 그렇게 쉬울리 없지
상위라는 이름이 괜히 나온게 아님....
만약 K가 2라면
나온 수가 2 이상인 숫자가 없는 경우 상위 2개에서 가져와야함
요소를 하나하나 검색하면서 했는데
관점을 바꿔야 겠음
일단 k 수 만큼 상위에 있는 놈들 다 가져오고...
Counter 정렬이 필요함 .most_common 방식을 쓰면 값을 기준으로 정렬이 됨
다만 리턴이 tuple로 된다는데 이건 또 뭔지 알아봐야겠음
뭔 안에 값을 통째로 던지나 일단 0으로 참조는 성공
'''
def topKFrequentMyway(self, nums: List[int], k: int) -> List[int]:
nums_counter = collections.Counter(nums).most_common()
result = []
for num in range(k):
result.append(nums_counter[num][0])
return result
'''
답안1: Counter를 이용한 음수 순 추출
새로운거 또 나옴
데이터를 정렬된 상태로 저장하기 위한 heapq 방식을 사용함
heapq 모듈은 이진 트리(binary tree) 기반의 최소 힙(min heap) 자료구조를 제공
최소 힙: 부모 노드의 키값이 자식 노드의 키값보다 항상 작은 힙
최대 힙: 부모 노드의 키값이 자식 노드의 키값보다 항상 큰 힙
암튼 최소 힙이면 낮은 수가 먼저 나옴
이제 중복 제거가 된 Counter를 for로 전개함
이때 heapq를 사용함
freqs_heap라는 변수에 데이터를 넣어주는데,
이때 key 값은 Counter된 value값
즉 나온 개수가 Key가 됨
여기서 Key값에 -를 붙여줌으로써 음수가 됨
즉 높은 숫자일수록 가장 작은 수로 바뀜
가장 많이 나온게 가장 먼저 정리되는 형식
key에는 나온 개수, value에는 해당 숫자를 넣어줌
heap은 이 데이터를 오름차순으로 정렬
이후에는 K 개수 만큼 heap에서 낮은 수를 꺼내주고 list에 추가해준뒤 반환
순서를 고려할때 heap을 염두에 둬야겠음
'''
def topKFrequentMywayCounter(self, nums: List[int], k: int) -> List[int]:
freqs = collections.Counter(nums)
freqs_heap = []
# 힙에 음수로 삽입
for f in freqs:
print(f'f: {f}')
print(f'freqs[f]: {freqs[f]}')
heapq.heappush(freqs_heap, (-freqs[f], f))
topk = list()
# k번 만큼 추출, 최소 힙(Min Heap)이므로 가장 작은 음수 순으로 추출
for _ in range(k):
topk.append(heapq.heappop(freqs_heap)[1])
return topk
'''
답안 2: 파이썬 다운 방식
아...또 뭔짓을 하기 시작했음
나도 썻지만 일단 most_common()으로 값이 높은 순서대로 아이템을 추출하는 기능을 사용
이때 most_common(k)를 통해 k 만큼만 반환
즉 원래
[(1, 3), (2, 2), (3, 1)] 이렇게 나와야 할 게 2개만 반환되서
[(1, 3), (2, 2)] 이렇게 됨
추출이기 때문에 새롭게 반환된 무언가(아마 튜플)에다가 zip()과 *을 사용함
zip() 함수는 2개 이상의 시퀀스를 짧은 길이를 기준으로 일대일 대응하는 새로운 튜플 시퀀스를 만듬....
[1, 2, 3, 4, 5] 애랑
[2, 3, 4, 5] 애를 석어서
[(1, 2), (2, 3), (3, 4), (4, 5)] 애를 만든다고 함
예시대로라면
[(1, 3), (2, 2)] 이놈을 zip을 통해서 1번요소는 1번 요소끼리, 2번 요소는 2번 요소끼리
즉 key끼리, value끼리 묶임
[(1, 2), (3, 2)]
*애는 여러 용도가 있지만 여기선 언팩키징으로 사용
즉 겉에 껍질 하나 제거해주는거
이 경우에는 튜플인 [(1, 2), (3, 2)]를
(1, 2), (3, 2)으로 바꾸고
list((1, 2), (3, 2))으로 행복한 리스트가 되었습니다.
마지막으로 [0]애는 첫번째 요소 가져오는거지 (1, 2) 리턴되고 끝
아무튼 별에별게 다 있음
'''
def topKFrequentMyway(self, nums: List[int], k: int) -> List[int]:
return list(zip(*collections.Counter(nums).most_common(k)))[0][총평]
새로운 자료구조 때마다 새로운 기능을 배우고 있다.
미리 책을 한번 다 읽어봤다면 좋았을텐데 아쉬움이 든다.
2일간 발표준비와 시험준비로 정신이 없었다.
계속 잠을 설쳐서 이젠 수면 패턴을 다시 좀 잡고 CS도 다시 잡고 가야겠다
정신이 많이 해이해진듯 하다.
달콤살벌