728x90 코딩 테스트101 [LeetCode] 2349. Design a Number Container System (Python) Problem Solutionhash change : 해당 index에 number를 저장하거나 이미 index에 Number 가 저장되어있으면 업데이트find: number에 대해서 어떤 인덱스에 존재하는지를 찾는다. number가 저장된 index 가 많으면 가장 최솟값 반환, 없으면 -1 반환 dict를 사용해야겠다고 생각했고 value 는 list로 구현해서 sorted 로 최솟값을 구해야겠다고 생각했다.그런데 SortedSet이 있는지 몰랐는데 이걸 사용하니 따로 sorted 를 안해주어도된다! 그리고 어떤 index 에 number 가 저장되어있는지 기록하는 변수 d,각 number 에 어떤 indicies들이 저장되어있는지 기록하는 변수 map 을 사용했다. Changechange 에서 ma.. 2025. 2. 8. [LeetCode] 3160. Find the Number of Distinct Colors Among the Balls (Python) Problem Solutionhashballs: x위치에 어떤 color 인지 저장count_colors: 특정 color 가 몇번 등장했는지 count 만약 x 위치의 공이 이미 색칠되어있다면, 해당 색상 - 1 Codeclass Solution: def queryResults(self, limit: int, queries: List[List[int]]) -> List[int]: n = len(queries) balls = dict() count_colors = defaultdict(int) answer = [] cnt = 0 for i in range(n): x, color = queries[i] .. 2025. 2. 8. [LeetCode] 1726. Tuple with Same Product (Python) Problem Solutionpermutation순열과 조합을 사용하여 푸는 문제.defaultdict 의 value를 리스트로 선언하여 2개의 integer 곱을 key로, tuple 을 value로 저장하였다.value 길이 (리스트)가 2 이상이면 value 길이만큼 8 x nC2 를 곱하여 경우의 수를 구하고 정답에 ++ 하였다.8을 곱하는 이유는 a*b = c*d 인 (a,b,c,d)의 경우의 수가 8이기 때문! ( 4permutation * 2 pairs)nC2를 한 이유는 value 길이 = n 에서 2개의 튜플을 선택해야되기 때문! Codefrom collections import defaultdictclass Solution: def tupleSameProduct(self, nums.. 2025. 2. 7. [LeetCode] 1800. Maximum Ascending Subarray Sum (Python) ProblemSolutionsliding window이전 문제와 유사하게 sub array 중 오름차순이면서 총 원소합의 최대값을 구하는 문제.num array 가 100 이하라서 2중 포문을 사용해되지만 최대한 fot문을 1번만 사용하려고했다. 강력한 힌트는 The end of each ascending subarray will be the start of the nextsubarray 만들고 체크한 마지막 인덱스가 다음 순회 인덱스의 첫번째 인덱스가 된다. 아래 코드에서 idx 가 그 역할. 아래는 더 깔끔한 코드가있어서 가져와봤다.아예 처음부터 처음 0번째 값을 넣은 리스트를 선언 후 증가하는 값이 나올때마다 리스트에 추가 (cur list)작아지는 숫자가 나오면 max 값 구하고 다시 cur li.. 2025. 2. 4. [LeetCode] 3105. Longest Strictly Increasing or Strictly Decreasing Subarray (Python) Problem Solutionsliding windowfor문으로 하나씩 값을 비교해가면서 decrease, increase 하는 sub array의 최대 길이값을 계산하는 문제.이때 strictly inc/dec 라서 동일한 숫자가 나오면 안된다. for문 하나로 해결하는게 관건! 처음에 아래 다른사람 코드처럼 increasing, decreasing 하는 로직으로 나누어서 푸려고했는데 간과한 점이 있었다.for문을 돌때 0번째가 아닌 1번 인덱스부터 앞 값과 비교할 것만약 increasing check 의 경우 nums[i] > num[i-1] 가 아니면 tmp_count =1 로 리셋할 것class Solution: def longestMonotonicSubarray(self, nums: Li.. 2025. 2. 3. [LeetCode] 1752. Check if Array Is Sorted and Rotated (Python) Problem SolutionBrute force처음에 무슨 문제인지 이해하기 어려웠던 문제어떤 위치 x 에서 일부를 잘라서 rotate 시키면 sorted array가 되는지 체크하는 문제.0번 또는 1번째에 만들 수 있으면 True, 아니면 False 반환 힌트를 보니 아래와 같이 적혀있었다.Brute force and check if it is possible for a sorted array to start from each position. class Solution: def checkSorted(self, arr): for i in range(len(arr) - 1): if arr[i] > arr[i + 1]: return Fal.. 2025. 2. 2. [LeetCode] 637. Average of Levels in Binary Tree (Python) Problem SolutiondequedefaultdictBinary Tree 문제로 같은 레벨의 노드의 합 평균값을 구하는 문제.값은 float 으로 반환해야된다.left/right node를 순회하면서 defaultidct에 각 레벨별 노드값을 저장한다.마지막에 defaultdict 에 저장된 데이터를 for문을 돌면서 합계와 평균값을 구한다. 아래는 다른 사람 풀이 중 하나def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]: queue = [root] ans = [] while queue: no_nodes_in_curr_level = len(queue) s.. 2025. 2. 1. [LeetCode] 3151. Special array 1 (Python) ProblemSolutionarray가 주어지면 양 옆 숫자로 두 쌍을 만들었을 때 differenct parity 가 만들어지는지 확인하는 문제우선 len(array) == 1 이면 무조건 True return그 이후에는 둘다 홀수 or 짝수인지 확인 후 맞으면 False, 아니면 continue굳이 동일 숫자인지 확인 안해도되었고, 홀/짝 경우로 나누지 않고 %2 나머지 값만 확인하면 된다!def isArraySpecial(self, nums: List[int]) -> bool: if len(nums) == 1: return True for i in range(len(nums)-1): if (nums[i] % 2) == (nums[i+1.. 2025. 2. 1. [LeetCode] 66.Plus One (Python) Problem Solutionstring1자리수 integer가 포함된 list 가 주어지고 이를 숫자로 변환 후 +1한 digit의 자리수를 list에 담아서 반환하는 문제.string -> int +1 -> string -> int 로 변환해서 풀었다.다른 사람 풀이를 보니 대부분 이렇게 푼듯 더 효율적인 코드는 아래와 같다.def plusOne(self, digits: List[int]) -> List[int]: n = len(digits) for i in range(n - 1, -1, -1): #n-1 부터 뒤에서 앞으로 반복한다. 즉 마지막 숫자부터 시작 if digits[i] 시간 복잡도는 digits 길이만큼 수행되므로 O(N)공간 복잡도는 dig.. 2025. 1. 31. [LeetCode] 125.Valid Palindrome (Python) Problem Solutionstring이전 Palindrome number 와 유사한 문제.대/소문자를 모두 대문자 or 소문자로 변환하고. , ! ? 와 같은 punctuation과 white space 을 제거 후 palindrome 인지 체크한다.이전에 파이썬 문법 중 string 을 거꾸로 뒤집는 방법을 알아서 string[::-1] 을 사용했다. 다른 사람의 풀이를 보니 isalnum() 메소드로 알파벳 or 숫자만 필터링하고 join 해서 아주 간단하게 풀었다.def isPalindrome(self, s: str) -> bool: s = ''.join([char for char in s if char.isalnum()]).lower() return s == s[::-.. 2025. 1. 31. [LeetCode] 1. Two Sum (Python) Problem Solutionhashhash를 사용해서 푸는 문제. 문제에서도 O(n^2) 보다 더 적은 시간 복잡도로 푸는것을 권장했다.아래는 1등 풀이class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: dt = {} for i, num in enumerate(nums): complement = target - num if complement in dt: return [dt[complement], i] dt[num] = i return [] 일반 for 문을 사용.. 2025. 1. 30. [LeetCode] 9. Palindrome Number (Python) Problemhttps://leetcode.com/problems/palindrome-number/description/?envType=study-plan-v2&envId=top-interview-150 Solutionarray정수 x 가 주어지면 앞뒤 거꾸로 바꾸어도 동일한 숫자가되는지 체크하는 문제.stack 을 사용하면되겠다고 생각했다. 몰랐는데 파이썬에서 string 을 거꾸로 뒤집는 방법이있었다 ㄷㄷ아래가 바로 그 코드s = str(x)return s == s[::-1] 다른 방법은 10으로 나눈 나머지를 tmp 변수에 * 10 하며서 더해준다.오리지널 x 는 10으로 나눈 몫으로 업데이트 해준다.class Solution: def isPalindrome(self, x: int) -> bo.. 2025. 1. 30. [LeetCode] 290.Word Pattern (Python) Problem Solutionarray 이전에 포스팅한 isomorphic string 과 동일한 문제.단지 스트링이 단순한 문자열이 아닌 단어로 이루어진 문장으로 변형한 문제.동일하게 sub string을 통해서 각 단어의 index 를 구한 후 pattern 과 비교하였다. Codeclass Solution: def wordPattern(self, pattern: str, s: str) -> bool: answer = False patternLi , sLi = [], [] for p in pattern: patternLi.append(pattern.index(p)) sub_str = s.split() .. 2025. 1. 28. [LeetCode] 205. Isomorphic String (Python) ProblemSolutionArray두 개의 문자열 s, t가 동형(isomorphic)인지 확인하는 문제. s에 존재하는 문자를 가지고 t를 만들 수 있으면 두 문자열 s, t는 동형이다. 단, 문자의 순서를 유지하며 모든 문자를 다른 문자로 바꿀 수 있어야한다. 두 문자가 같은 문자로 맵핑되어서는 안된다. 처음에 dictionary로 character 개수만 카운트해서 비교했는데 알고보니 문제 이해를 잘 못했다.엣지 케이스인 s = bbbaaaba, t = aaabbbba 에서 마지막에서 두번째 문자에서 조건을 만족하지 못하므로 falseCodeclass Solution: def isIsomorphic(self, s: str, t: str) -> bool: answer = False.. 2025. 1. 28. [LeetCode] 202. Happy Number (Python) 1. 문제https://leetcode.com/problems/happy-number/description/?envType=study-plan-v2&envId=top-interview-1502. 풀이Hash 를 사용한 기본 문제. 문제 이해를 완벽하게 못해서 헤맸다.각 자리수를 제곱하여 sum 하는 사이클을 돌다가 만약 1로 끝나면 happy number 이므로 return true 아니면 return falsen=2 인 경우 2 -> 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4 (cycle 발생)즉 방문했던 숫자를 또 방문하면 return false를 반환해야한다. 3. 코드class Solution: def isHappy(self, n: int) -.. 2025. 1. 27. [HackerRank] Contacts (Python) 1.문제https://www.hackerrank.com/challenges/contacts/problem 2.풀이처음에 정직하게 구현으로 풀다가 time limit exceeded 나서 실패..단순해 보이지만 Time Complexity를 신경써서 풀어야하는 문제이다.def contacts(queries): answer = [] arr = [] for i in range(len(queries)): command = queries[i][0] if command == 'add': data = queries[i][1] arr.append(data) else: target = queries[i][1].. 2025. 1. 18. [HackerRank] Find the Running Median (Python) 1. 문제https://www.hackerrank.com/challenges/find-the-running-median/problem 2. 풀이처음엔 a의 길이가 홀수, 짝수 케이스로 나누어서 단순히 중위값을 구하려고했다.참고로 python에서 n / 2 를 하면 실수를 반환하지만 n//2를 하면 int 정수를 반환한다.def runningMedian(a): answer = [] for i in range(1, len(a)+1): li = sorted(a[:i]) n = len(li) # odd if (n % 2 != 0): median = li[n // 2] else: med.. 2025. 1. 18. [HackerRank] Tree: Level Order Traversal 1. 문제https://www.hackerrank.com/challenges/tree-level-order-traversal/problem 2. 풀이처음에 preOrder 문제로 잘 못 생각한 문제. 레벨을 기준으로 순회를 해야한다.아래 코드는 preOrder 코드def levelOrder(root): if root is None: return print(root.info) levelOrder(root.left) levelOrder(root.right) 레벨 기준으로 순회하려면 BFS 와 같이 queue를 사용해야한다.다른 사람 풀이를 보니 stack 과 queue 의 장점을 모두 가지고 있는 deque를 사용해서 deque 를 사용해서 해결한다. queue 의 inse.. 2025. 1. 18. [HackerRank] Tree: Height of a Binary Tree (Python) 1. 문제https://www.hackerrank.com/challenges/tree-height-of-a-binary-tree/problem 2. 풀이Binary의 가장 높은 height를 구하는 문제.현재 root node 가 None이면 -1 반환재귀함수를 이용해서 왼쪽노드와 오른쪽 노드의 height 구한다. 시간 복잡도 : O(N) - 모든 노드를 한번씩 방문하므로 시간 복잡도는 N, N은 여기서 노드 수공간 복잡도 : O(H) - 재귀호출 스택의 공간 복잡도는 트리의 높이 H 와 동일 3. 코드def height(root): if root is None: return -1 depth_left = height(root.left) depth_right = height.. 2025. 1. 18. [HackerRank] Balanced Brackets (Python) 1. 문제https://www.hackerrank.com/challenges/balanced-brackets/problem 2.풀이stack을 이용한 기본 문제 3.코드def isBalanced(s): st = [] print(s) for i in range(len(s)): if (s[i] == "(" or s[i] == "{" or s[i] == "["): st.append(s[i]) elif s[i] == ")": if (len(st) 0): return "NO" return "YES" 4.리팩토링dictionary 사용해서 중복된 코드 제거하기def isBalanced(s): stack = [].. 2025. 1. 18. 이전 1 2 3 4 5 6 다음 728x90
