kwang2134 님의 블로그

[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 ..

[NeetCode-LeetCode] Number of 1 Bits - Easy접근비트 연산풀이주어진 정수를 2진수로 변환했을 때 해밍 웨이트를 구하는 문제이다. 해밍 웨이트(Hamming weight)는 2진수에서 0의 개수를 제외한 1의 개수라고 생각하면 된다. 예를 들어 n = 11 일 때 11은 2진수로 1011이고 1의 개수가 3개이므로 해밍 웨이트는 3이 된다.  가장 간단하고 직관적인 방법으로 2진수로 변환을 한 뒤 직접 1의 개수를 세는 방법이다. public int hammingWeight(int n) { String binary = Integer.toBinaryString(n); int result = 0; for (char c :..

[NeetCode-LeetCode] Same Tree - Easy 접근재귀풀이주어진 두 트리가 같은 지 검증하면 되는 문제이다. 트리의 값과 형태를 기준으로 검증하기 때문에 재귀를 통해 같은 레벨 같은 위치에 같은 값이 존재하는지만 확인하면 되는 문제로 간단한 문제이다. public boolean isSameTree(TreeNode p, TreeNode q) { return checkSameTree(p, q); } private boolean checkSameTree(TreeNode p, TreeNode q) { if (p == null && q == null) { return true; } if (p =..

[NeetCode-LeetCode] Binary Search - Easy접근이진 탐색풀이NeetCode의 문제들 중 grind75에서 풀었던 문제를 제외하고 난이도 순으로 풀다 보니 easy 문제에선 기초적인 알고리즘 구현 문제가 나와 다시 돌아보는 느낌으로 푸는 중이다. 이번 문제는 이진 탐색 구현 문제이다. 정말 이진 탐색에 대해서만 구현하는 문제로 target이 주어지고 배열에서 이진 탐색을 통해 target의 인덱스를 반환하면 된다. 정말 친절하게 배열도 미리 정렬된 상태로 주어진다.  코드는 너무 간단하니 이진 탐색에 대해 다시 돌아보고 넘어가자면 이진 탐색은 O(logn)을 만족하는 탐색 방법으로 연산 한 번 수행마다 범위를 절반씩 줄여나가며 탐색을 진행하기 때문에 log의 n 시간 복잡도를 ..