kwang2134 님의 블로그

[Grind75-LeetCode] Partition Equal Subset Sum - Medium접근dpdfs풀이주어진 정수 배열 내의 값을 동등한 부분 합으로 만들 수 있는지 검사하는 문제이다. 예제 1번처럼nums = [1,5,11,5] -> [1, 5, 5] and [11]동일한 부분합으로 분리할 수 있는지 확인하는 것이다. 예제 1번이 [1, 5, 5]와 [11]로 분리되어 원소들을 더 한 값이 배열에 존재하는가와 같은 문제 이해를 잘못할 수 있는데 nums = [3,3,3,4,5] -> [3,3,3] and [4,5] 위처럼 단순히 부분합이 같은 두 집합으로 분리하는 것이다. public boolean canPartition(int[] nums) { int target = 0;..

[Grind75-LeetCode] Word Break - Medium접근dpdfsdfs + 메모이제이션풀이주어진 문자열 s를 단어 List에 들어있는 단어들로 구성이 가능한지 검사하는 문제이다. List에 들어있는 단어들은 중복이 없고 여러 번 사용이 가능하다. 문제 이해자체는 굉장히 쉽기 때문에 테스트케이스만 봐도 이해할 수 있다.  처음 접근으로 replace를 사용해 List에 들어있는 단어들을 공백으로 치환한 뒤 순회가 끝나고 문자열이 공백이 되었다면 만들 수 있는 것으로 true, 문자가 남아있다면 false를 반환하게 만들어봤다.  public boolean wordBreak(String s, List wordDict) { for (String word : wordDict) ..

[Grind75-LeetCode] Sort Colors - Medium접근Dutch National Flag풀이이 문제는 0, 1, 2가 들어있는 배열을 라이브러리의 sort 함수를 사용하지 않고 오름차순으로 정렬하면 되는 문제이다. 추가로 외부에 추가적인 공간을 사용하지 않고 배열 내부의 움직임으로만 one-pass 즉 한 번의 순회로 정렬해 보라는 추가 문제도 있다. 우선 Arrays.sort()를 사용해 제출을 해도 0ms의 최고 성능으로 통과는 가능하다. 그러나 문제의 취지와는 어긋나기에 라이브러리를 사용하지 않고 구현해야 한다. 우선 자바의 Arrays.sort()는 원시 타입 배열를 기준으로 Dual-Pivot QuickSort 알고리즘을 통해 정렬된다. Dual-Pivot QuickSort는..

[Grind75-LeetCode] Accounts Merge - Medium 접근dfsUnion-Find풀이2차원 리스트로 사용자의 이름과 보유한 이메일 정보가 주어진다. 각accounts [i][0]는 사용자의 이름을 나타내고 1번 인덱스부턴 보유 이메일이 들어있다. 이번 문제는 사용자가 보유한 중복되는 이메일을 병합하는 문제로 동명이인은 가려내고 같은 사용자의 이메일은 병합해 깔끔하게 출력하는 것이 목표이다. accounts = [["John","johnsmith@mail.com","john_newyork@mail.com"], ["John","johnsmith@mail.com","john00@mail.com"], ["Mary","mary@mail.com"], ["John","jo..

[Grind75-LeetCode] Time Based Key-Value Store - Medium접근이진 탐색객체풀이시간을 베이스로 한 Key-Value 형식의 맵을 구현하는 문제이다. String 값으로 주어지는 Key가 있고 int 타입의 timestamp와 String 타입 value가 있다. 구현해야 할 TimeMap은 set, get 두 가지 메서드를 가지고 있으며 구현해야 할 오늘의 목표이다.  TimeMap의 작동 방식은 다음과 같다. Key와 Value 형태로 저장하는 Map과 동일하나 Key에 해당하는 Value에는 timestamp가 있다 즉 시간대별로 저장된 값을 따로 분리해야 한다. 한 Key에는 여러 timestamp가 존재하고 timestamp 마다 각각의 Value를 가지고 있..

[Grind75-LeeCode] Lowest Common Ancestor of a Binary Tree - Medium접근dfs풀이이진트리에서 최저 공통 조상 노드를 찾는 문제이다. 이전에 거의 흡사한 문제를 풀었던 적이 있다.2024.10.08 - [알고리즘/코딩테스트-Grind75] - [Grind75-LeetCode] Lowest Common Ancestor of a Binary Search Tree JAVA [Grind75-LeetCode] Lowest Common Ancestor of a Binary Search Tree JAVA[Grind75-Leetcode] Lowest Common Ancestor of a Binary Search Tree - EasyLowest Common Ancestor..

[Grind75-LeetCode] Merge Intervals - Medium 접근구현풀이2차원 배열로 구간이 주어지면 겹치는 구간을 합쳐 반환하는 문제이다. 이전에 풀었던 구간 삽입 문제와 비슷한 듯 다른 문제이다. intervals = [[1,3],[2,6],[8,10],[15,18]] -> intervals = [[1,6],[8,10],[15,18]]1~3 + 2~6 병합 -> 1~6위와 같이 구간이 들어있는 배열이 존재할 때 겹치는 범위를 병합하여 병합된 배열을 반환하는 문제이다. 내가 풀었던 방법을 먼저 설명하고 더 성능이 좋았던 다른 코드를 몇 개 들고 와 분석할 예정이다. public int[][] merge(int[][] intervals) { List result = n..

[Grind75-LeetCode] Permutations - Medium 접근dfs풀이주어지는 배열로 만들 수 있는 모든 숫자 조합을 반환하는 문제이다. 더 자세히 말하면 조합이라기보다 배열의 원소들을 재배열해서 만들 수 있는 순서쌍을 모두 구하는 것이 맞는 것 같다. 배열이 [1, 2, 3] 일 경우 [1], [1, 2]와 같은 조합을 구하는 것이 아니라 [1, 2, 3], [1, 3, 2]처럼 모든 요소를 사용한 조합이기 때문에 재배열할 수 있는 경우의 수를 모두 반환하는 것이다.  public List> permute(int[] nums) { List> result = new ArrayList(); dfs(nums, new ArrayList(), result); ..

[Grind75-LeetCode] Combination Sum - Medium접근dfs풀이주어지는 정수 배열의 요소들을 사용해 target을 만들 수 있는 모든 조합을 구하는 문제이다. 배열에는 중복된 원소가 존재하지 않고 각 요소를 무한히 사용이 가능하다. 전에 풀었던 동전 문제와 유사하나 이번에는 최소 개수를 구하는 것이 아닌 모든 조합을 구해야 하므로 dfs를 사용해 풀어주었다.  public List> combinationSum(int[] candidates, int target) { List> result = new ArrayList(); List ls = new ArrayList(); dfs(candidates, target, 0, ls, result..

[Grind75-LeetCode] Search in Rotated Sorted Array - Medium접근이진 탐색 (Binary Search)풀이배열 내부에 순환이 있는 정렬된 배열에서 특정 원소를 찾아 인덱스를 반환하는 문제이다. 해당 문제는 O(log n)의 시간 복잡도를 가진 알고리즘으로만 통과가 가능하다. 대표적인 탐색 알고리즘에서 범위를 절반씩 줄여가며 진행하는 이진 탐색이 O(log n)으로 이 문제도 이진 탐색을 통해 해결된다.  이 문제의 포인트는 주어지는 배열이 단순하게 정렬된 배열이 아니라는 것이다. 정렬되어 있긴 하지만 내부에 순환점이 존재해nums = [4,5,6,7,0,1,2]위와 같은 형태로 0번 인덱스가 제일 작은 값이 아니고 마지막 인덱스가 제일 큰 값이 아닌 상태로 주어..