Today_I_Learned/Algorithm
-
99클럽 코테 스터디 16일차 TIL: 스택/큐, Leetcode 921. Minimum Add to Make Parentheses ValidToday_I_Learned/Algorithm 2024. 6. 25. 23:33
문제https://leetcode.com/problems/minimum-add-to-make-parentheses-valid/description/통과 여부Pass 나의 접근(오답) 처음에는 짝이 맞지 않는 괄호의 수를 세면 된다고 생각했다.(반례) 하지만 괄호의 짝은 모두 맞지만 방향이 다른 경우도 있었다. 결국 stack 을 사용하게 되었다.문자열을 순회하며 '(' 는 push 하고, ')' 을 만나면 stack 에서 pop 을 하도록 한다.')' 를 만났는데 stack 이 비어있으면 s 를 완성하기 위한 문자 삽입 횟수를 +1 한다.class Solution: def minAddToMakeValid(self, s: str) -> int: ans = 0 stack = [..
-
99클럽 코테 스터디 15일차 TIL: 스택/큐, Leetcode 2390. Removing Stars From a StringToday_I_Learned/Algorithm 2024. 6. 24. 22:48
문제https://leetcode.com/problems/removing-stars-from-a-string/description/ 통과 여부Pass 나의 접근문자열을 순회하며 문자를 하나씩 string 변수에 붙인다. * 을 만나면 string 변수의 마지막 문자를 제거한다.시간 복잡도 측면에서 더 좋은 방법 (항해99 스터디를 통해 알게 된 방법)stack 에 넣고, * 이 나오면 stack 을 pop 한다.class Solution: def removeStars(self, s: str) -> str: ans = '' for c in s: if c != '*': ans += c else: ..
-
99클럽 코테 스터디 14일차 TIL: 스택/큐, Leetcode 341. Flatten Nested List IteratorToday_I_Learned/Algorithm 2024. 6. 24. 00:02
문제https://leetcode.com/problems/flatten-nested-list-iterator/description/ 통과 여부Fail 문제 해석깊이의 제한이 없는 중첩 List 들을 1차원 List 로 해체시켜야 함. 나의 접근다음 요소가 List 일 때 재귀를 이용하여 제일 깊이 있는 List 요소부터 stack 에 push 함.재귀가 끝나면 stack 의 요소를 하나씩 pop 하여 별도의 1차원 List 에 담기.하지만 문제는 아직 못 풀음... 재도전 하는 것으로.
-
99클럽 코테 스터디 13일차 TIL: 스택/큐, Leetcode 1823. Find the Winner of the Circular GameToday_I_Learned/Algorithm 2024. 6. 22. 18:32
문제https://leetcode.com/problems/find-the-winner-of-the-circular-game/description/ 통과 여부Pass 나의 접근법 1 부터 n 까지 구성된 List 'q' 생성매 Turn 마다 k 번째에 있는 요소 탐색 => target = k % len(q) (만약 index 가 0부터 시작이면 -1 을 해주어야 함.)매 Turn 마다 target 을 제거하고 q 를 갱신. q = 'target 이후의 List' + 'target 이전까지의 List'q 의 길이가 1이 될 때까지 반복class Solution: def findTheWinner(self, n: int, k: int) -> int: q = [e+1 for e ..
-
99클럽 코테 스터디 12일차 TIL: 정렬, Leetcode 869. Reordered Power of 2Today_I_Learned/Algorithm 2024. 6. 21. 21:10
문제https://leetcode.com/problems/reordered-power-of-2/description/ 통과 여부Fail 나의 접근법 주어진 숫자를 재조합하는 문제였으므로 당연히 순열을 사용해 풀어야한다고 생각했다.먼저 끝자리가 짝수로 끝나는 수열을 모두 구한 후 2의 거듭제곱인지를 확인하는 것이었다. (2의 거듭제곱인지 확인하는 방법: https://hkim-data.tistory.com/179)그러나 순열을 구현하는 방법을 몰랐던 나는 결국 컨닝을 하게 되었는데 순열을 사용하지 않는 신박한 방법이 있었다.바로 2의 거듭제곱 수에 사용된 숫자들의 빈도수와 주어진 정수를 이루는 숫자들의 빈도수가 일치하는 지 확인하는 것이다.(!!!) https://81shinez.tistory.com/27..
-
99클럽 코테 스터디 11일차 TIL: 배열, Leetcode 347. Top K Frequent ElementsToday_I_Learned/Algorithm 2024. 6. 20. 23:00
문제https://leetcode.com/problems/top-k-frequent-elements/description/ 통과 여부Fail -> Pass 나의 접근법 num 를 순회하며 각 element 의 count 를 별도의 dict 에 count:[num,..] 으로 저장dict 의 key 로 정렬하려 앞에서부터 k까지의 key 에 속하는 value(숫자) 를 Return ... 이라는 거창한 계획을 세웠었는데항해 정규 스터디 시간을 통해 python 의 collections 에서 most_common() 이라는 함수를 제공하고 있다는 사실을 알게 되었다. 이 함수를 사용하면 1 줄 coding 이 가능해진다!!!python 을 이런 utility 함수들이 많이 제공되고 있다보니 배열같은 문제에..
-
99클럽 코테 스터디 10일차 TIL: 배열, Leetcode 451. Sort Characters By FrequencyToday_I_Learned/Algorithm 2024. 6. 19. 20:08
문제https://leetcode.com/problems/sort-characters-by-frequency/description/ 통과 여부Pass 나의 접근법 첫 번째 방법class Solution: def frequencySort(self, s: str) -> str: # 문자 - 빈도수로 dict 초기화 : 중복되는 문자 제거 char_frq = {} for ch in s: if ch in char_frq: char_frq[ch] += 1 else: char_frq[ch] = 1 # (빈도수, 문자) 쌍을 갖는 배열을 빈도..
-
99클럽 코테 스터디 9일차 TIL: 배열, 1529. Minimum Suffix FlipsToday_I_Learned/Algorithm 2024. 6. 19. 00:11
문제https://leetcode.com/problems/minimum-suffix-flips/description/ 통과 여부Fail 나의 접근법 XOR 문제는 풀이 경험 부족 탓에 접근법에 대한 감이 1도 없었다. 하여 다른 사람들이 정리한 글들을 참고하였다.참고: https://blog.naver.com/PostView.naver?blogId=babobigi&logNo=222042107759&parentCategoryNo=&categoryNo=30&viewDate=&isShowPopularPosts=false&from=postView LeetCode) 1529. Bulb Switcher IV문제 https://leetcode.com/contest/weekly-contest-199/problems/b..