동까의 코딩

항해99 코딩테스트 스터디 2기는 오늘이 마지막입니다.마지막 문제는 leetcode의 2405입니다.https://leetcode.com/problems/optimal-partition-of-string/submissions/1302935018/ 문제 풀이1. 문자열을 차례대로 반복문을 구현해준다.2. 중복되지 않은 문자를 넣어 줄 리스트를 생성하여 저장한다.3. 리스트에 없다면 문자를 계속해서 넣어주고, 겹치는 것이 나오면 리스트를 리셋해주고 해당 문자를 넣어주고 cnt를 1 더해준다.4. 만약에 반복문이 끝나고, 리스트가 들어있다면 cnt를 1 더해줍니다. class Solution: def partitionString(self, s: str) -> int: cnt = 0 ..

이제 마지막 정규 스터디가 종료되었습니다. 그래도 매일 TIL 적는 습관을 가져가보도록 하겠습니다. https://leetcode.com/problems/reduce-array-size-to-the-half/submissions/1302135035/ class Solution: def minSetSize(self, arr: List[int]) -> int: N = len(arr) nums = defaultdict(int) for num in arr: nums[num] += 1 nums = sorted(nums.items(), key = lambda x: x[1], reverse=True) ..

https://leetcode.com/problems/seat-reservation-manager/submissions/1300708018/ heap의 기본적인 동작을 나타내는 문제입니다. from collections import dequeclass SeatManager: def __init__(self, n: int): self.min_heapq = [i for i in range(1, n + 1)] def reserve(self) -> int: return heapq.heappop(self.min_heapq) def unreserve(self, seatNumber: int) -> None: heapq.heappush(self.min_heapq, ..

https://leetcode.com/problems/minimum-add-to-make-parentheses-valid/submissions/1299761990/ 오늘의 문제는 괄호 스택 문제입니다. 예전에 스택 관련해서 문제를 많이 풀어봐서 빠르게 풀게되었습니다. 먼저 (가 입력되면 stack에 채워줍니다. 그리고 )닫히는 괄호가 나오면 pop을 해줘서 stack에서 최근 것을 빼줍니다.하지만 stack이 비어있을 때 )가 입력되는 경우도 있으니 이 때는 카운트를 해줍니다.그리고 마지막으로 stack에 ( 입력이 쌓여있을 수 있으니 카운트 값에 마지막에 stack의 들어있는 개수만큼 더해주어 구현하였습니다. class Solution: def minAddToMakeValid(self, s: st..

https://leetcode.com/problems/removing-stars-from-a-string/submissions/1298504525/ class Solution: def removeStars(self, s: str) -> str: st = [] for i in s: if i == '*' and len(st) != 0: st.pop() else: st.append(i) answer = "" if len(st) != 0: for i in st: answer += i return answer..

https://leetcode.com/problems/flatten-nested-list-iterator/ class NestedIterator(object): def __init__(self, nestedList): def dfs(nestedList): for item in nestedList: if item.isInteger(): self.stack.append(item.getInteger()) else: dfs(item.getList()) self.stack = [] dfs(nestedList) d..

https://leetcode.com/problems/find-the-winner-of-the-circular-game/ class Node: def __init__(self, v): self.val = v self.next = None self.prev = Noneclass Solution: def findTheWinner(self, n: int, k: int) -> int: start_node = cur_node = Node(1) prev_node = None for i in range(2, n + 1): new_node = Node(i) cur_node.next = new_n..

https://leetcode.com/problems/reordered-power-of-2/description/ import itertoolsclass Solution: def reorderedPowerOf2(self, n: int) -> bool: cnt = 0 answer = False n = str(n) num_list = [] for i in n: num_list.append(i) nCr = itertools.permutations(num_list, len(num_list)) num_list = [] nCr = list(nCr) for i in range(le..