오늘은 해시테이블에 대해 배웠다. 처음 강의만 보고는 잘 이해가 안되서 유튜브 영상을 추가로 학습했다.
https://www.youtube.com/watch?v=ZBu_slSH5Sk
문제를 풀면서 sorted() 함수의 매개변수에 대해 알게 되었다.
- iterable (반복 가능한 객체): 정렬하고자 하는 요소들이 담긴 iterable 객체이다. 주로 리스트나 튜플 등을 사용한다.
- key (정렬 기준 함수): 정렬 기준을 지정하는 함수이다. 기본값은 None이며, 이 경우 요소 자체를 비교하여 정렬한다. 사용자가 직접 정렬 기준을 지정하려면 이 매개변수를 사용한다.
- reverse (정렬 순서): 정렬 순서를 지정하는 매개변수로, 기본값은 False이다. True로 설정하면 내림차순으로 정렬된다.
- key와 reverse 매개변수는 선택적이며, 생략할 수 있다. 만약 둘 다 생략된다면 기본적으로 오름차순으로 정렬된다.
1번 문제 771. Jewels and Stones
class Solution:
def numJewelsInStones(self, jewels: str, stones: str) -> int:
s_count = {}
for stone in stones:
if stone in s_count:
s_count[stone] +=1
else:
s_count[stone] = 1
count = 0
for j in jewels:
if j in s_count:
count += s_count[j]
return count
solution = Solution()
딱히 어렵지 않았다. 그저 해시테이블에 stone에 해당하는 count값을 value로 넣어주기만 하면되는 문제다.
2번 문제 3. Longest Substring Without Repeating Characters
LeetCode - The World's Leading Online Programming Learning Platform
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
def lengthOfLongestSubstring(self, s: str) -> int:
long = 0
s_count ={}
count = 0
for char in s:
if char in s_count:
s_count[char] += 1
else:
s_count[char] = 1
for char in s:
if s_count[char] == 1:
count += 1
long = max(long, count)
else:
count = 0
long = max(long, count)
return long
*미해결
해시태이블에 s를 넣고 중복되는 횟수을 측정해서 그 측정값이 1인 경우를 찾아내려고 했는데 그렇게 되면 무조건 count가 0이 되서 잘못된 접근 방법이었던것 같다. 그래서 고민하다가 도저히 모르겠어서 gpt를 이용했다.
def lengthOfLongestSubstring(s: str) -> int:
max_length = 0
start = 0
char_index_map = {}
for i, char in enumerate(s):
if char in char_index_map and char_index_map[char] >= start:
start = char_index_map[char] + 1
char_index_map[char] = i
max_length = max(max_length, i - start + 1)
return max_length
# Example 1
s1 = "abcabcbb"
print(lengthOfLongestSubstring(s1)) # Output: 3
# Example 2
s2 = "bbbbb"
print(lengthOfLongestSubstring(s2)) # Output: 1
# Example 3
s3 = "pwwkew"
print(lengthOfLongestSubstring(s3)) # Output: 3
중복되지 않는 부분 문자열의 시작 인덱스를 start 변수에 기억하고 이전에 등장한 문자의 인덱스를 해시 맵에 저장하고, 만약 해당 문자가 현재 부분 문자열에 포함되어 있고 그 인덱스가 현재 부분 문자열의 시작보다 크거나 같다면 시작 인덱스를 업데이트한다. 그렇지 않으면 현재 부분 문자열의 길이를 계산하여 최대 길이와 비교하여 업데이트하는 방식이다.
3번 문제 347. Top K Frequent Elements
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
n_count = {}
for num in nums:
if num in n_count:
n_count[num] += 1
else:
n_count[num] = 1
sorted_counts = sorted(n_count.items(), key=lambda x: x[1], reverse=True)
result = []
for i in range(k):
result.append(sorted_counts[i][0])
return result
크게 어렵진 않았으나 해시테이블을 정렬하는 방법을 잘 몰라서 검색을 했는데 람다함수 이용하라고 했다.
*람다
람다 함수는 간단한 함수를 한 줄로 작성할 때 유용하며, 주로 함수를 인자로 받는 함수나 리스트 등의 컬렉션을 다룰 때 자주 사용된다. lambda x: x[1]은 리스트나 튜플 등의 요소 중에서 인덱스가 1인 값을 반환한다. 이러한 람다 함수는 정렬할 때 각 요소를 기준으로 하고자 할 때 사용된다.
4번 문제 수 찾기
class Solution:
def test4(self, N, M, A, check):
table = {}
for i in A:
table[i] = True
result = []
for j in check:
if j in table:
result.append(1)
else:
result.append(0)
return result
N = int(input())
A = list(map(int, input().split()))
M = int(input())
check = list(map(int, input().split()))
sol = Solution()
print(*sol.test4(N, M, A, check), sep='\n')
특별할건 없었다.
5번 문제(박경민)
class main:
def test5(self, N, M, inputs):
personal = {}
for _ in range(N):
site, password = inputs.pop(0).split()
personal[site] = password
for _ in range(M):
site_to_find = inputs.pop(0)
print(personal[site_to_find])
N, M = map(int, input().split())
inputs = []
for _ in range(N+M):
inputs.append(input())
m = main()
m.test5(N, M, inputs)
예제와 출력의 숫자를 더해서 한꺼번에 입력받고 배열에 넣은뒤 예제 만큼의 횟수를 pop해서 해시테이블에 넣고 나머지 횟수를 해시테이블에서 pop해서 출력하는 방식으로 해결했다. 코드리뷰할때 배운것은 input에 비해 sys.stdin가 훨씬 처리시간 측면에서 적합하다고 한다.
*추가 공부
- enumerate
- for 문에서 주로 사용되고 처리속도 측면에서 활용적이다.
- Counter 함수
- 요소 개수 세기: 반복 가능한 객체의 요소들을 세어 그 개수를 딕셔너리 형태로 반환한다.
- 요소의 빈도 확인: 특정 요소의 빈도를 확인할 수 있다.
- 산술 연산 지원: 두 개의 Counter 객체 간의 합, 차, 교집합 등의 산술 연산을 지원한다.
- heapq.nlargest(n, iterable, key=None)
함수는 주어진 반복 가능한(iterable) 객체에서 가장 큰 n개의 요소를 찾아 리스트로 반환한다.
이 함수는 힙(heap) 자료구조를 사용하여 구현되어 있어, 크기가 n인 최대 힙을 만들어 가장 큰 n개의 요소를 찾는다.
- n: 반환할 요소의 개수를 지정합니다.
- iterable: 요소를 찾을 반복 가능한 객체입니다.
- key: 비교 기준이 되는 함수를 지정할 수 있습니다. 기본값은 None이며, 이 경우 요소들의 크기를 비교하여 최대값을 찾습니다. 키 함수를 지정하면 해당 함수를 적용한 결과를 기준으로 요소들을 비교합니다.
heapq.nlargest() 함수의 시간 복잡도는 O(n + klogn)이며, 여기서 n은 반복 가능한 객체의 길이이고, k는 반환할 요소의 갯수이다. 따라서 일반적으로 반환할 요소의 갯수가 n보다 훨씬 작은 경우에 효율적으로 사용할 수 있다.