kwang2134 님의 블로그

[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 시간 복잡도를 ..

[NeetCode-LeetCode] Single Number - Easy접근MapXOR풀이배열의 원소중 중복이 없는 원소를 찾는 문제이다. 배열의 원소들은 모두 2개씩 존재하나 단 한 개의 원소만 2개가 아닌 1개만 존재한다. 문제를 푸는 것 자체는 쉽기 때문에 여러 가지 방법으로 풀 수 있다.  public int singleNumber(int[] nums) { Map map = new HashMap(); for (int num : nums) { map.merge(num, 1, Integer::sum); } for (Integer i : map.keySet()) { if (map.get(i) == 1) { ..

[NeetCode-LeetCode] Kth Largest Element in a Stream - Easy접근힙 (우선순위 큐)풀이스트림에 있는 요소에 K번째로 큰 요소를 반환하는 문제이다. 처음 생성자를 호출하고 원소를 추가하는 add 연산만 구현하면 된다. add 연산 수행 시 요소를 추가하고 K 번째 요소가 어떤 것인지 반환하면 된다. 우선순위 큐의 문제라 적혀있던 만큼 우선순위 큐를 통해 구현하면 간단하게 풀 수 있는 문제이다.class KthLargest { private PriorityQueue minHeap; private int k; public KthLargest(int k, int[] nums) { this.k = k; minHeap = new P..

[NeetCode-LeetCode] Valid Sudoku - Medium접근브루트 포스풀이Grind75에 있던 문제를 다 풀고 NeetCode로 넘어왔다. NeetCode에서 겹치치 않는 안 풀었던 문제를 위주로 풀어볼 예정이다. 첫 번째 문제로 스도쿠를 검증하는 문제이다. 말 그대로 주어진 스도쿠 판이 스도쿠 규칙을 만족하고 있는지 검사하는 문제이다. 처음 문제를 봤을 때 주어진 스도쿠 판으로 스도쿠를 완성할 수 있는지를 검사하는 문제인 줄 알고 그냥도 완성하기 힘든 스도쿠를 완성할 수 있는지 검사하라니 Medium 난이도가 맞는가 싶어 요구하는 시간 복잡도를 봤더니 n의 제곱이었다. n의 제곱이라는 뜻은 주어진 스도쿠 2차원 배열을 한 번만 방문해서 완성하라는 의미인데 그게 가능한가 싶어 생각해 보..

[Grind75-LeetCode] Largest Rectangle in Histogram - Hard접근스택풀이Grind75의 마지막 문제로 히스토그램에서 가장 큰 사각형의 넓이를 구하는 문제이다. 이렇게 넓이를 구하는 유사한 문제에선 거의 슬라이딩 윈도우나 투 포인터를 사용했었지만 이번 문제는 끝 포인터들의 길이만 체크하는 것이 아니기 때문에 사용하기 어려운 방법이다.  어떻게 보면 더 간단한 방법일 수 있는데 스택을 사용해 푸는 것이다. 스택에 배열을 순회하며 값을 넣는다. 이전 스택에 들어있는 peek 값과 다음 진행에서 현재 인덱스의 값을 비교해 peek 값 보다 현재 인덱스 값이 크다면 스택에 값을 추가한 뒤 넘어가고 현재 인덱스 값이 작다면 스택에서 값을 꺼내 계산해 주면 된다. 쉽게 말해 스..

[Grind75-LeetCode] Merge k Sorted Lists - Hard 접근우선순위 큐분할 정복버킷 정렬풀이ListNode 객체를 정렬된 상태로 병합하는 문제이다. ListNode 객체는 필드로 값과 다음 ListNode의 참조 값을 가지고 있다. 이 문제를 봤을 때 주어진 노드의 순서를 알 맞게 배열해 하나의 ListNode로 만들어라는 말이겠지만 과연 채점 기준으로 객체의 참조값을 비교해 볼까?라는 생각이 들었다. 만약 참조 값을 기준으로 채점하지 않는다면 그냥 값들을 순서에 맞게 새로운 객체를 만든 뒤 반환하면 되기 때문이다. 코드가 복잡하지 않으니 한 번 해봤다. public ListNode mergeKLists(ListNode[] lists) { PriorityQu..

[Grind75-LeetCode] Maximum Profit in Job Scheduling - Hard접근dp이진 탐색풀이Job 스케줄러를 통해 얻을 수 있는 최대 이득을 구하는 문제이다. 시작 시간이 들어있는 배열, 종료 시간이 들어있는 배열 그리고 이익 값이 들어있는 배열이 주어진다. Job은 비선점 방식으로 수행이 되며 어떤 작업이 끝나는 시간에 다른 작업을 시작할 수 있다. 각 작업의 시간과 이득을 객체로 합쳐 놓고 종료시간을 기준으로 정렬한 뒤 dp와 이진 탐색을 통해 풀면 된다. 풀었던 방법과 성능이 제일 좋았던 코드는 알고리즘 자체는 동일하고 리스트를 사용하냐 배열을 사용하냐 정도의 차이였기 때문에 성능이 제일 좋았던 배열을 사용한 코드를 바로 들고 왔다. class Job { ..

[Grind75-LeetCode] Basic Calculator - Hard 접근스택풀이기본적인 계산기를 구현하는 문제로 문자열로 입력받은 수식을 계산한 결과를 반환하면 되는 문제이다. 수식에는 괄호가 포함될 수 있고 - 연산자는 단항 연산자로 사용이 될 수 있다. 즉 +의 경우 +1과 같이 앞에 다른 값 없이 단항 연산자로 사용될 수 없지만 -의 경우 -1과 같이 단항 연산자로 수식에서 사용될 수 있다.  무엇보다 이 문제에서 연산자는 +, - 두 가지만 존재한다. 곱하기 나누기 연산이 존재하지 않다 보니 괄호에 대한 처리만 스택을 통해 천천히 해주면 어렵지 않게 해결이 가능하다. public int calculate(String s) { Stack stack = new Stack()..