HTTP:! HTTP:!

주어진 리스트에서 빈도수를 세어놓고, k순위만큼 출력하는 문제 collection.Counters를 사용하면 쉽게 풀린다. def topKFrequent(self, nums: [], k: int) -> []: lst = collections.Counter(nums).most_common(k) return [l[0] for l in lst] 책에서는 heap을 사용해서 했던데, 방법이 신기했다. def topKFrequent(self, nums: [], k: int) -> []: freqs = collections.Counter(nums) freqs_heap = [] for f in freqs: heapq.heappush(freqs_heap, (-freqs[f], f)) print(freqs_heap) t..

가장 긴 부분 문자열 찾는 문제, 단 문자열 안에 중복이 없어야 한다. 나는 for문 2번 돌려서 풀긴했는데, 만약 input의 길이가 증가하면 시간 초과 날것이다. def lengthOfLongestSubstring(self, s: str) -> int: ans = 0 for idx, ch in enumerate(s): cnt = 0 c = "" for ch in s[idx:]: if ch in c: break else: c += ch cnt += 1 ans = max(ans, cnt) return ans 이전에 배운 hash를 여기서 사용하면 for문 한번과 hash 접근으로 가능하다. def lengthOfLongestSubstring(self, s: str) -> int: max_length = ..

jewel이 stone에 몇개 들어있는지 세어보는 문제 1) 이중 for문 int numJewelsInStones(string J, string S) { int cnt = 0; for (int i = 0; i int: cnt = 0 for s1 in stones: if s1 in jewels: cnt += 1 return cnt 3) dict 이용 def numJewelsInStones(self, jewels:str, stones:str)->int: # J의 각 문자가 S에 몇개 들어있는지 파악하면 되는 문제 freq = {} count = 0 for ss in stones: if ss in freq: freq[ss] = 1 else: freq[ss] += 1 for char in jewels: if c..

해시맵 디자인 하는 문제 (파이썬은 Dict가 해시맵으로 볼 수 있다.) 해시맵 이론들... 해시맵에서 충돌했을때 해결 방법은 개별체이닝과 오픈어드레싱 방법이 있다. 개별 체이닝 - LinkedList로 데이터를 이어나가는 방법(O(n)도 걸릴수 있다.) 오픈어드레싱 - 충돌이 났을때, 그 주변을 선형으로 탐색해 적절한 위치에다 넣는것, (모든 원소가 반드시 자신의 해쉬값과 일치한다는 보장이 없음) 파이썬은 오픈어드레싱을 사용하고 있다. 해시맵 로드팩터 - 해시 테이블에 저장된 데이터 개수 n을 버킷의 개수 k로 나눈것 파이썬의 로드팩터는 0.66이고, 자바는 0.75이다. 이 비율을 넘어가면 각 언어에서 해시 테이블 공간을 재할당 한한다. import sys from itertools import co..

ListNode를 가진 List들을 정렬해서 하나의 ListNode로 만드는 문제이다. 두 가지 방법이 있다. 1) ListNode를 한번 씩 다 거쳐서, 새로운 list를 만들고, 다시 ListNode로 만드는 방법 def mergeKLists(self, lists: List[ListNode]) -> ListNode: head = point = ListNode(0) node = [] for item in lists: # 2차원 배열에서 하나씩 가져와서 [0]번의 ListNode부터 끝번까지 돌면서 val만 저장 #it = item[0] while item: node.append(item.val) item = item.next for x in sorted(node): point.next = ListNod..

deQueue 구현 문제 deQueue는 이중 연결리스트로 많이 구현한다. (left, right) 앞, 뒤로 추가 가능하다. head와 tail은 제일 앞에 ListNode와 맨 뒤의 ListNode를 가르키고 있다. 만약 제일 앞에 새로운 값을 추가하려면, head를 새로운 ListNode를 가르키게 하고, 이전 값을 연결해주면 된다. head, tail에서 add를 공통으로 하기 위해서 오른쪽에 추가하는걸 기준으로 _add함수를 만들었다. del 역시 공통으로 사용하기 위해서 오른쪽 자식을 삭제하는걸 기준으로 잡았다. add, del시에 tail에서는 어느 부분을 가르켜야되는지 손으로 그려보면 잘 알 수 있다. class MyCircularDeque: def __init__(self, k: int)..

Circle Queue(원형 큐)를 구현해보자 원형 큐는 일반적인 큐와 다르게 끝나는 지점이 다시 시작으로 이어져서 기존 큐의 단점을 극복가능하다. (기본 큐는 지나온 지점을 다시 재활용이 불가능하다.) 구현 방법에는 일반적으로는 front와 rear, 두 포인터를 가지고 구현을 한다. 또한, 배열에 특별한 값(None)을 사용해서 현재 사용중인지 아닌지 구분한다. class MyCircularQueue: def __init__(self, k: int): self.front = 0 self.rear = 0 self.queue = [None] * k self.len = k def enQueue(self, value: int) -> bool: # rear 지점에 None일 경우에는 비어 있는 상태 if se..

stack을 이용해서 queue를 구현하는 것 python의 list는 특정 index에서도 remove가 가능하다. queue명령어들은 다음과 같다. void push(int x) Pushes element x to the back of the queue. -> queue의 맨 뒤에 넣으면 되겠다/ int pop() Removes the element from the front of the queue and returns it. -> queue의 맨 앞을 pop하면 되겠다. int peek() Returns the element at the front of the queue. -> queue의 맨 앞의 원소 boolean empty() Returns true if the queue is empty, f..