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차원 배열을 한 번만 방문해서 완성하라는 의미인데 그게 가능한가 싶어 생각해 보..