kwang2134 님의 블로그

[NeetCode-LeetCode] Pacific Atlantic Water Flow - Medium접근bfsdfs풀이태평양과 대서양으로 물이 흘러갈 수 있는지 확인하는 문제이다. 문제를 읽었을 때 이해가 빠르게 되는 문제는 아니었다. 좌표에는 물의 깊이 값이 들어있고 특정 좌표에서 물은 상하좌우로 흐를 수 있고 좌표의 다음 칸이 기존 좌표의 값과 동일하거나 더 작아야 흘러갈 수 있다는 그런 내용인 거 같았다. 결론은 특정 좌표에 물이 두 바다에 모두 도달이 가능한 지 체크하는 문제인 것 같았다.  그렇다면 양쪽 바다에서 시작해 모든 좌표를 체크하고 도달 가능한 두 좌표가 겹치는 부분을 찾으면 될 것이다.  private static final int[] dx = {-1, 1, 0, 0}; p..

[NeetCode-LeetCode] Design Add and Search Words Data Structure - Medium 접근접근 방법풀이단어 추가와 검색을 가능이 가능한 데이터 구조를 디자인하는 문제이다. 단어 추가의 경우 입력받는 단어를 데이터 구조 내 저장하는 로직을 수행하고 검색의 경우 데이터 구조 검색하고자 하는 단어가 저장되어 있는지 확인하는 로직이다. trie 파트에 있는 문제로 trie를 사용하여 풀어야 하는 문제로 전에 풀었던 문제는 검색 단어가 그대로 주어졌기 때문에 특별히 신경 쓸 부분이 없었지만 이번에는 "." 점의 형태로 패턴 매칭을 수행해야 하기 때문에 좀 더 복잡해졌다고 볼 수 있다. 기존 삽입 부분과 베이스는 이전에 풀었던 코드를 그대로 들고왔다. class Node ..

[NeetCode-LeetCode] Subtree of Another Tree - Easy접근재귀풀이어떤 트리 내부에 동일한 서브트리가 존재하는지 검사하는 문제이다. 정확하게 주어진 서브트리와 일치해야 한다 즉 기존 트리 내부에 서브트리와 동일한 부분이 존재하지만 밑에 추가로 자식 노드가 존재하거나 하는 경우엔 동일한 서브트리라 볼 수 없다. 위와 같은 형태에 왼쪽 트리에 4, 1, 2라는 동일한 구조가 있는데 2 노드 밑에 0이라는 자식 노드가 있기 때문에 다른 서브트리라 판단하고 false가 된다.  public boolean isSubtree(TreeNode root, TreeNode subRoot) { if (root == null) { return false..

[NeetCode-LeetCode] Find Minimum in Rotated Sorted Array - Medium접근이진 탐색 (Binary Search)풀이회전된 배열에서 최솟값을 찾는 문제이다. 배열은 정렬된 상태로 회전되어 있고 원소 중 최솟값을 찾는 문제로 사실 답을 구하는 것 자체는 굉장히 쉬운 문제이다. 배열을 한 번만 순회해도 간단하게 풀 수 있는 너무 간단한 내용이지만 난이도가 Medium인 이유는 O(log n)의 시간 복잡도로 문제를 해결해야 하기 때문이다.  일반적으로 배열을 한 번 순회한다면 O(n) 시간 복잡도로 요구 조건을 만족하지 못한다. 그러므로 O(log n)을 만족시키기 위해선 이진 탐색을 사용해 문제를 해결해야 한다. 이진 탐색은 한 번의 탐색마다 범위를 절반으로 줄..

[NeetCode-LeetCode] Consecutive Sequence - Medium접근TreeSetstream풀이배열의 원소 내에 연속된 수열이 존재하는지 찾고 존재한다면 수열의 길이가 최대 길이가 몇 인지 반환하는 문제이다. 우선 배열은 정렬되지 않고 원소의 중복이 존재하는 형태로 주어지는 것 같다. 그렇기 때문에 편하게 해결하기 위해선 중복과 정렬을 수행해주어야 하는데 중복과 정렬이라고 하니 TreeSet이 생각이 나 사용해 봤다.  TreeSet은 Set과 같이 중복된 원소를 포함하지 않는 자료구조인데 HashSet과의 차이점으론 내부적으로 Tree 구조를 사용해 원소를 저장하므로 원소들이 자동으로 정렬된 상태로 관리된다. 이는 원소가 삽입될 때 Tree의 적당한 위치에 배치되기 때문인데 Tr..

[NeetCode-LeetCode] Top K Frequent Elements - Medium 접근map버킷 정렬(Bucket Sort)풀이각 원소들의 빈도수를 상위 K 개만큼 반환하는 문제이다. Arrays & Hashing 분야에 있는 문제다 보니 HashMap을 사용해서 쉽게 풀 수 있을 거 같은 생각은 있으나 추가 질문으로 요구하는 O(n log n)을 만족하지는 못할 것 같다.  처음 풀었던 방법은 빈도를 map을 사용해 세어준 뒤 스트림을 사용해 value 값 내림차순으로 정렬을 하고 k 개 limit를 걸어 배열로 변환하여 반환하는 방법이었다. public int[] topKFrequent(int[] nums, int k) { Map frequentMap = new Hash..

[NeetCode-LeetCode] Group Anagrams - Medium접근map풀이애너그램을 만족하는 문자열끼리 그룹을 만들어 반환하는 문제이다. 애너그램이란 같은 문자로 이루어진 문자열들을 생각하면 된다. eat과 tea는 둘 다 a, e, t로 이루어진 문자열로 애너그램이라고 할 수 있다. 즉 문자열을 구성하는 문자가 같도록 그룹을 지어주면 되는 것이다.  가장 간단하게 생각하면 애너그램이란 같은 문자로 이루어져 있기 때문에 정렬을 할 경우 같은 형태로 변하게 된다. 각 값들을 정렬을 하여 비교하게 되면 쉽게 구할 수 있을 거 같았지만 기본적으로 문자열 전체를 한 번 순회하는데 n 각 문자열을 정렬하는데 문자열 길이만큼 k log k라는 시간이 소요되기 때문에 결국 n * k log k라는 시..

[NeetCode-LeetCode] Missing Number - Easy 접근수학풀이배열에 들어있지 않는 숫자를 찾는 문제이다. 배열은 0번지부터 시작하기 때문에 0부터 값을 순차적으로 채운다고 할 때 배열의 크기가 n일 경우 n - 1 번째 숫자까지 채워지게 된다. 즉 0부터 숫자를 채우는 경우 n까지의 숫자를 채우기 위해선 n + 1의 크기를 가진 배열이 필요하다. 이 문제는 크기가 n인 배열에 n까지의 숫자를 채워 넣어 주게 되는데 자리가 없어 들어가지 못한 한 개의 숫자를 찾아내는 문제이다. 문제를 푸는 것 자체는 간단하게 두 번의 반복으로 손쉽게 풀 수 있다. 새로운 체크용 배열을 생성해 존재하는 값들은 체크를 해두어 풀면 된다. public int missingNumber(int[] n..

[NeetCode-LeetCode] Revers Bits - Easy접근비트 조작풀이이번 문제는 이진수로 주어진 값을 거꾸로 뒤집었을 때의 값을 출력하는 문제로 부호 없는 정수라는 가정하에 수행한다. 부호 없는 정수는 말 그대로 이진수로 이루어진 값을 계산한 정수 값으로 각 비트의 자리의 값을 계산하기만 하면 된다. 부호 있는 정수의 경우 맨 앞자리의 비트가 0인지 1 인지로 부호를 판단하게 된다. 맨 앞자리 비트가 0인 경우 양수로 똑같이 이진수 값을 변환하듯 하면 되지만 맨 앞자리 비트가 1인 경우 음수로 2의 보수를 통해 구해진다. 2의 보수를 통해 구하는 법은 모든 비트가 1인 수와 XOR 연산을 통해 기존 비트가 1이면 0이 되고 0이면 1이 되게 반전을 시키고 1을 더한 값을 계산한 뒤 부호를..

[NeetCode-LeetCode] Counting Bits - Easy접근비트 연산풀이0부터 정수 n까지의 모든 숫자에 1이 몇 개 포함되어 있는가 구하는 문제이다.  n = 5 라면 0, 1, 2,..., 3, 4, 5 각 숫자의 1 개수를 배열에 담아 반환하면 된다. 이전 Number of 1 Bits와 같이 비트 조작 유형에 속하는 문제로 비트 연산자를 사용해야 하는 문제인 것 같다.  비트 조작 문제도 맞지만 dp를 사용해야 하는 문제이다. dp를 사용하지 않아도 풀 수는 있어서 난이도가 easy인지 모르겠는데 dp와 비트 조작을 같이 써서 풀면 easy라 하기엔 조금 난이도가 있지 않나? 싶다. public int[] countBits(int n) { int[] result ..