Merge branch 'main' of https://github.com/sungjinwi/leetcode-study

DaleStudy · Jan 3, 2025 · 929ae16 · 929ae16
2 parents 06701b1 + 5c4c12a
commit 929ae16
Show file tree

Hide file tree

Showing 175 changed files with 5,398 additions and 1 deletion.
diff --git a/3sum/Yjason-K.ts b/3sum/Yjason-K.ts
@@ -0,0 +1,53 @@
+/**
+ * 세 수의 합이 0이 되는 모든 고유한 조합을 찾는 함수
+ * 
+ * @param {number[]} nums - 정수 배열
+ * @returns {number[][]} - 세 수의 합이 0이 되는 조합 배열
+ * 
+ * 1. 입력 배열 `nums`를 오름차순으로 정렬.
+ * 2. 이중 반복문을 사용하여 각 요소를 기준으로 `투 포인터(two-pointer)`를 이용해 조합을 탐색.
+ * 3. 중복 조합을 방지하기 위해 `Set`을 사용하여 결과 조합의 문자열을 저장.
+ * 4. 조건에 맞는 조합을 `result` 배열에 추가합니다.
+ * 
+ * 시간 복잡도:
+ * - 정렬: O(n log n)
+ * - 이중 반복문 및 투 포인터: O(n^2)
+ * - 전체 시간 복잡도: O(n^2)
+ * 
+ * 공간 복잡도:
+ * - `Set` 및 `result` 배열에 저장되는 고유 조합: O(k), k는 고유한 조합의 수
+ * - 전체 공간 복잡도: O(n + k)
+ */
+function threeSum(nums: number[]): number[][] {
+    const sumSet = new Set<string>();
+    const result: number[][] = [];
+    nums.sort((a, b) => a - b);
+
+    // 첫 번째 요소를 기준으로 반복문 수행
+    for (let i = 0; i < nums.length - 2; i++) {
+        // 정렬 된 상태이기 때문에 시작점을 기준으로 다음 값 중복 비교
+        if (i > 0 && nums[i] === nums[i - 1]) continue;
+
+        let start = i + 1, end = nums.length - 1;
+        while (start < end) {
+            const sum = nums[i] + nums[start] + nums[end];
+            if (sum > 0) {
+                end--;
+            } else if (sum < 0) {
+                start++;
+            } else {
+                const triplet = [nums[i], nums[start], nums[end]];
+                const key = triplet.toString();
+                if (!sumSet.has(key)) {
+                    sumSet.add(key);
+                    result.push(triplet);
+                }
+                start++;
+                end--;
+            }
+        }
+    }
+
+    return result;
+}
+
diff --git a/binary-tree-level-order-traversal/Gotprgmer.java b/binary-tree-level-order-traversal/Gotprgmer.java
@@ -0,0 +1,53 @@
+/**
+ * Definition for a binary tree node.
+ * public class TreeNode {
+ *     int val;
+ *     TreeNode left;
+ *     TreeNode right;
+ *     TreeNode() {}
+ *     TreeNode(int val) { this.val = val; }
+ *     TreeNode(int val, TreeNode left, TreeNode right) {
+ *         this.val = val;
+ *         this.left = left;
+ *         this.right = right;
+ *     }
+ * }
+ */
+
+// preorder에서 맨 왼쪽을 root
+// root값을 기반으로 inorder에서 인덱스를 찾는다 그리고 왼쪽 오른쪽 길이를 구한다.
+// 다시 buildTree 함수를 재귀하는데 이때 위에서 구한 왼쪽 길이와 오른쪽길이를 참고해서
+// 왼쪽 buildTree
+// value를 갱신
+// 오른쪽 buildTree를 갱신한다.
+
+// 시간복잡도 : O(N^2) -> 한쪽으로 치우친 트리일 경우 O(N)(index of) + T(N-1)이 될 수 있다.
+// 위 식을 전개해보면 N + N-1 + N-2 + ... + 1 = N(N+1)/2 = O(N^2)
+// 공간복잡도 : O(N) ->리트코드 but N길이의 리스트 크기*N번의 재귀호출이 일어날 수 있다. 따라서 O(N^2)가 아닌가...?
+class SolutionGotprgmer {
+    public TreeNode buildTree(int[] preorder, int[] inorder) {
+
+        if(preorder.length == 0 || indexOf(inorder,preorder[0]) == -1){
+            return null;
+        }
+        TreeNode node = new TreeNode();
+
+        int root = preorder[0];
+        int indexOfRoot = indexOf(inorder,root);
+        int leftCnt = indexOfRoot;
+        // 찾으면
+        node.val = root;
+        node.left = buildTree(Arrays.copyOfRange(preorder,1,1+leftCnt),Arrays.copyOfRange(inorder,0,leftCnt));
+        node.right = buildTree(Arrays.copyOfRange(preorder,1+leftCnt,preorder.length),Arrays.copyOfRange(inorder,1+leftCnt,inorder.length));
+        return node;
+    }
+    public int indexOf(int[] intArray,int findNum){
+        for(int i=0;i<intArray.length;i++){
+            if(findNum==intArray[i]){
+                return i;
+            }
+        }
+        return -1;
+    }
+
+}
diff --git a/coin-change/Chaedie.py b/coin-change/Chaedie.py
@@ -0,0 +1,28 @@
+"""
+직접 풀지 못해 알고달레 풀이를 참고했습니다. https://www.algodale.com/problems/coin-change/
+
+Solution:
+    1) BFS를 통해 모든 동전을 한번씩 넣어보며 amount와 같아지면 return
+
+(c: coins의 종류 갯수, a: amount)
+Time: O(ca)
+Space: O(a)
+"""
+
+
+class Solution:
+    def coinChange(self, coins: List[int], amount: int) -> int:
+        q = deque([(0, 0)])  # (동전 갯수, 누적 금액)
+        visited = set()
+
+        while q:
+            count, total = q.popleft()
+            if total == amount:
+                return count
+            if total in visited:
+                continue
+            visited.add(total)
+            for coin in coins:
+                if total + coin <= amount:
+                    q.append((count + 1, total + coin))
+        return -1
diff --git a/coin-change/jinah92.py b/coin-change/jinah92.py
@@ -0,0 +1,10 @@
+# O(C*A) times, O(A) spaces
+class Solution:
+    def coinChange(self, coins: List[int], amount: int) -> int:
+       dp = [0] + [amount + 1] * amount
+
+       for coin in coins:
+            for i in range(coin, amount + 1):
+                dp[i] = min(dp[i], dp[i-coin]+1)
+
+       return dp[amount] if dp[amount] < amount + 1 else -1
diff --git a/coin-change/minji-go.java b/coin-change/minji-go.java
@@ -0,0 +1,23 @@
+/*
+    Problem: https://leetcode.com/problems/coin-change/
+    Description: return the fewest number of coins that you need to make up that amount
+    Concept: Array, Dynamic Programming, Breadth-First Search
+    Time Complexity: O(NM), Runtime 15ms   - M is the amount
+    Space Complexity: O(M), Memory 44.28MB
+*/
+class Solution {
+    public int coinChange(int[] coins, int amount) {
+        int[] dp = new int[amount+1];
+        Arrays.fill(dp, amount+1);
+        dp[0]=0;
+
+        for(int i=1; i<=amount; i++){
+            for(int coin : coins){
+                if(i >= coin) {
+                    dp[i] = Math.min(dp[i], dp[i-coin] +1);
+                }
+            }
+        }
+        return dp[amount]>amount? -1: dp[amount];
+    }
+}
diff --git a/coin-change/pmjuu.py b/coin-change/pmjuu.py
@@ -0,0 +1,25 @@
+from typing import List
+
+
+class Solution:
+    def coinChange(self, coins: List[int], amount: int) -> int:
+         # dp[i]: i 금액을 만들기 위해 필요한 최소 동전 개수
+        dp = [float('inf')] * (amount + 1)
+        dp[0] = 0
+
+        for i in range(1, amount + 1):
+            for coin in coins:
+                if coin <= i:
+                    dp[i] = min(dp[i], dp[i - coin] + 1)
+
+        return dp[amount] if dp[amount] != float('inf') else -1
+
+
+# 시간 복잡도:
+# - 외부 반복문은 금액(amount)의 범위에 비례하고 -> O(n) (n은 amount)
+# - 내부 반복문은 동전의 개수에 비례하므로 -> O(m) (m은 coins의 길이)
+# - 총 시간 복잡도: O(n * m)
+
+# 공간 복잡도:
+# - dp 배열은 금액(amount)의 크기만큼의 공간을 사용하므로 O(n)
+# - 추가 공간 사용은 없으므로 총 공간 복잡도: O(n)
diff --git a/combination-sum/Chaedie.py b/combination-sum/Chaedie.py
@@ -0,0 +1,35 @@
+"""
+Solution:
+    최초 풀이 당시엔 단순히 dfs로 풀었으나 시간 초과로 실패했습니다.
+    이후 풀이 설명을 통해 i 번째 숫자를 넣거나 / 안넣거나 라는 조건으로 i를 늘려가도록 진행하는 백트래킹을 하면 된다는점을 배웠습니다. 
+    이를 통해 불필요한 중복을 줄이고 효율적인 구현이 가능해집니다.
+
+C: len(candidates)
+T: target size
+
+Time: O(C^T) = 라고 설명되어 있는데 솔찍히 잘 모르겠습니다.
+Space: O(T) = 재귀가 가장 깊을 때 [1,1,1,1...] T 만큼이기 때문에 O(T)
+"""
+
+
+class Solution:
+    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
+        result = []
+        sol = []
+        n = len(candidates)
+
+        def backtrack(i, cur_sum):
+            if cur_sum == target:
+                result.append(sol.copy())
+                return
+            if cur_sum > target or i == n:
+                return
+
+            backtrack(i + 1, cur_sum)
+
+            sol.append(candidates[i])
+            backtrack(i, cur_sum + candidates[i])
+            sol.pop()
+
+        backtrack(0, 0)
+        return result
diff --git a/combination-sum/GangBean.java b/combination-sum/GangBean.java
@@ -0,0 +1,43 @@
+class Solution {
+    public List<List<Integer>> combinationSum(int[] candidates, int target) {
+        /**
+        1. understanding
+        - find all combinations, which sum to target
+        - can use same number multiple times
+        2. strategy
+        - dp[target]: all combination, which sum to target
+        - dp[n + 1] = dp[n] | dp[1]
+        - [2,3,6,7], target = 7
+            - dp[0] = [[]]
+            - dp[1] = [[]]
+            - dp[2] = [[2]]
+            - dp[3] = [[3]]
+            - dp[4] = dp[2] | dp[2] = [[2,2]]
+            - dp[5] = dp[2] | dp[3] = [[2,3]]
+            - dp[6] = dp[2] | dp[4] , dp[3] | dp[3] = [[2,2,2], [3,3]]
+            - dp[7] = dp[2] | dp[5], dp[3] | dp[4], dp[6] | dp[1], dp[7] = [[2,2,3],]
+        3. complexity
+        - time: O(target * N) where N is length of candidates
+        - space: O(target * N)
+        */
+        List<List<Integer>>[] dp = new List[target + 1];
+        for (int i = 0; i <= target; i++) {
+            dp[i] = new ArrayList<>();
+        }
+
+        dp[0].add(new ArrayList<>());
+
+        for (int candidate : candidates) {
+            for (int i = candidate; i <= target; i++) {
+                for (List<Integer> combination : dp[i - candidate]) {
+                    List<Integer> newCombination = new ArrayList<>(combination);
+                    newCombination.add(candidate);
+                    dp[i].add(newCombination);
+                }
+            }
+        }
+
+        return dp[target];
+    }
+}
+
diff --git a/combination-sum/HerrineKim.js b/combination-sum/HerrineKim.js
@@ -0,0 +1,30 @@
+// 시간 복잡도 : O(n^2)
+// 공간 복잡도 : O(n)
+
+/**
+ * @param {number[]} candidates
+ * @param {number} target
+ * @return {number[][]}
+ */
+
+var combinationSum = function(candidates, target) {
+  const result = [];
+
+  const backtrack = (remaining, combo, start) => {
+      if (remaining === 0) {
+          result.push([...combo]);
+          return;
+      }
+
+      for (let i = start; i < candidates.length; i++) {
+          if (candidates[i] <= remaining) {
+              combo.push(candidates[i]);
+              backtrack(remaining - candidates[i], combo, i);
+              combo.pop();
+          }
+      }
+  };
+
+  backtrack(target, [], 0);
+  return result;
+};
diff --git a/combination-sum/HodaeSsi.py b/combination-sum/HodaeSsi.py
@@ -0,0 +1,16 @@
+# 시간복잡도 : O(n * m) (n: target, m: len(candidates))
+# 공간복잡도 : O(n * m)
+class Solution:
+    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
+        dp = [[] for _ in range(target + 1)]
+        dp[0] = [[]]
+
+        for candidate in candidates:
+            for num in range(candidate, target + 1):
+                for combination in dp[num - candidate]:
+                    temp = combination.copy()
+                    temp.extend([candidate])
+                    dp[num].append(temp)
+
+        return dp[target]
+
diff --git a/combination-sum/Real-Reason.kt b/combination-sum/Real-Reason.kt
@@ -0,0 +1,23 @@
+package leetcode_study
+
+fun combinationSum(candidates: IntArray, target: Int): List<List<Int>> {
+    val result = mutableListOf<List<Int>>()
+    val nums = ArrayDeque<Int>()
+    dfs(candidates, target, 0, 0, nums, result)
+
+    return result
+}
+
+private fun dfs(candidates: IntArray, target: Int, startIdx: Int, total: Int, nums: ArrayDeque<Int>, result: MutableList<List<Int>>) {
+    if (target < total) return
+    if (target == total) {
+        result.add(ArrayList(nums))
+        return
+    }
+    for (i in startIdx..< candidates.size) {
+        val num = candidates[i]
+        nums.add(num)
+        dfs(candidates, target, i, total + num, nums, result)
+        nums.removeLast()
+    }
+}
diff --git a/combination-sum/Zioq.js b/combination-sum/Zioq.js
@@ -0,0 +1,44 @@
+/**
+ * @param {number[]} candidates
+ * @param {number} target
+ * @return {number[][]}
+ */
+var combinationSum = function(candidates, target) {
+    let result = [];
+
+    function find_combination(index, target, current) {
+        if (target === 0) {
+            result.push([...current]);
+            return;
+        }
+
+        for (let i = index; i < candidates.length; i++) {
+            // Only proceed if current number doesn't exceed target
+            if (candidates[i] <= target) {
+                // Include current number in combination
+                current.push(candidates[i]);
+
+                // Recursive call with:
+                // - same index i (allowing reuse of same number)
+                // - reduced target by current number
+                find_combination(i, target - candidates[i], current);
+
+                // Backtrack: remove the last added number to try other combinations
+                current.pop();
+            }
+        }
+    }
+
+    find_combination(0, target, []);
+    return result;
+};
+
+/* 
+
+
+
+*/
+
+console.log(combinationSum([2,3,6,7], 7))
+
+