HTTP:! HTTP:!

가장 긴 부분 문자열 찾는 문제, 단 문자열 안에 중복이 없어야 한다. 나는 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..

Queue를 이용해서 Stack을 구현하는 문제 python에서는 list에서 stack도 가능하고 queue도 가능하지만, list를 queue처럼 사용할 경우 속도가 느리다. O(1)을 보장하기 위해 Queue를 사용한다. 문제에서는 일단 list를 사용해서 myStack을 만들었고, 통과를 했음 class MyStack: def __init__(self): self.q = [] def push(self, x: int) -> None: self.q.append(x) def pop(self) -> int: return self.q.pop() def top(self) -> int: return self.q[-1] def empty(self) -> bool: return len(self.q) == 0 하지..