kwang2134 님의 블로그

[NeetCode-LeetCode] Design Twitter - Medium접근구현풀이트위터의 기능을 디자인하는 문제로 포스팅, 피드 보기, 팔로우, 언팔로우를 구현해야 하는 문제이다. 기존 sns와 동일하게 유저는 포스트를 작성할 수 있고, 자기 자신의 포스트와 팔로우하는 유저의 포스트를 볼 수 있으며 다른 유저를 팔로우, 언팔로우할 수 있다. 주의할 부분은 포스트를 얻는 부분으로 포스트는 최신 10개의 포스트를 가져와야 한다. 최신 10개의 포스트라는 것은 해당 유저가 팔로우하는 유저에 따라 변경되는 부분으로 특정 유저를 팔로우하기 시작했다면 다시 최신 10개의 포스트를 구성해야 하고 언팔로우하였다면 언팔로우한 유저의 포스트를 뺀 최신 10개를 다시 구성해야 한다. 즉 포스트 요청 시 동적으로 구성..

[NeetCode-LeetCode] Max Area of Island - Medium접근dfs풀이2차원 배열이 주어지고 1로 이루어진 구간의 최대 넓이를 구하는 문제이다. 비슷한 유형이 많은 문제이기 때문에 dfs를 통해 간단하게 해결해 주면 된다.  private static final int[] dx = {0, 0, 1, -1}; private static final int[] dy = {1, -1, 0, 0}; public int maxAreaOfIsland(int[][] grid) { int answer = 0; for (int i = 0; i grid의 값이 1인 경우에 dfs를 실행하여 넓이를 구하게 된다.  private int dfs(int[]..

[NeetCode-LeetCode] Koko Eating Bananas - Medium접근이진 탐색 풀이바나나 개수가 담긴 배열이 주어지고 시간이 주어질 때 모든 바나나를 다 먹는데 걸리는 최소 시간당 바나나 개수를 구해야 한다. 코코는 한 시간의 k개만큼 바나나를 먹을 수 있는데 모든 바나나를 제한 시간 안에 먹어야 할 때 시간당 먹어야 하는 바나나의 개수인 k의 최솟값을 구하는 문제이다.  바나나 더미의 최대 개수가 매우 큰 값이기 때문에 이진 탐색을 통해 구해주었다. public int minEatingSpeed(int[] piles, int h) { int left = 1; int right = 1000000000; while (left 더미의 최소 개수..

[NeetCode-LeetCode] Combination Sum II - Medium 접근dfs 풀이주어진 배열 내 숫자들을 한 번씩만 사용해 target 값을 만들 수 있는 조합을 모두 찾아내는 문제이다. 숫자들은 한 번씩만 사용이 가능하며 중복된 조합은 포함하면 안 된다.  단순하게 dfs를 사용해 모든 경우를 탐색하면 되는데 목표로 맞춰야 하는 값이 존재하기 때문에 그 값을 기준으로 백트래킹을 통한 불필요한 값을 걸러주면 되는 문제이다.  public List> combinationSum2(int[] candidates, int target) { List> result = new ArrayList(); Arrays.sort(candidates); dfs(c..

[NeetCode-LeetCode] Last Stone Weight - Easy 접근힙풀이배열에 돌의 무게가 주어지고 두 개의 돌을 부딪혀 새로운 무게의 돌을 만들어 낼 때 마지막에 남는 돌의 무게를 반환하는 문제이다. 두 돌의 무게가 같다면 모두 부서져 사라지고 무게가 다를 경우 무거운 돌의 무게에서 가벼운 돌의 무게를 뺀 만큼의 무게를 가진 돌이 새로 생기게 된다. 돌은 무거운 순서대로 부딪히게 되어 우선순위 큐를 사용해 주면 간단하게 해결할 수 있는 문제이다. public int lastStoneWeight(int[] stones) { PriorityQueue pq = new PriorityQueue((a,b) -> b - a); for (int stone : sto..

[NeetCode-LeetCode] Search a 2D Matrix - Medium 접근이진 탐색풀이오름차순으로 정렬된 2차원 배열에서 target 값이 존재하는지 찾는 문제이다. O(log(m * n))의 시간 복잡도로 해결을 하라고 되어 있는 이진 탐색 카테고리의 문제이다. 2차원 배열에서 이진 탐색을 사용하기 위해 2차원 좌표를 그대로 사용해 한 번 풀어보려 했으나 범위 조정이 매끄럽게 되지 않고 효율적이지 못해 그만뒀다. public boolean searchMatrix(int[][] matrix, int target) { int start = 0; int end = matrix.length * matrix[0].length - 1; while (sta..

[NeetCode-LeetCode] Daily Temperatures - Medium 접근스택풀이배열에 기온이 주어지고 각 인덱스의 기온보다 더 따뜻한 날이 며칠 뒤에 오는지 구하는 문제이다. 스택을 사용하는 문제로 인덱스 값을 스택으로 관리하면 해결할 수 있다.  public int[] dailyTemperatures(int[] temperatures) { int[] answer = new int[temperatures.length]; Stack stk = new Stack(); for (int i = 0; i temperatures[stk.peek()]) { int index = stk.pop(); ..

[NeetCode-LeetCode] Two Integer Sum II - Medium접근투 포인터풀이정렬된 배열이 주어질 때 배열 내 두 원소를 더 해 target 값을 만드는 경우 두 원소가 위치한 순서를 반환하는 문제이다. 배열이 [2, 7, 11, 15]이고 target = 9인 경우에 9를 만들기 위해 0번지의 2와 1번지의 7을 더하면 되는데 인덱스 값을 반환하는 것이 아니라 인덱스에 1을 더한 값을 반환해야 한다. 테스트는 정확하게 1개의 해가 나오게 주어지기 때문에 항상 성공이 가능한 경우라고 보면 된다. 추가로 상수 공간만 사용해서 해결하라는 조건도 있다.  public int[] twoSum(int[] numbers, int target) { int start = 0; ..

[NeetCode-LeetCode] Sum of Two Integers - Medium접근비트 조작풀이단순하게 두 수를 더하는 문제인데 +, - 연산자를 사용하지 않고 두 수의 합을 구하는 문제이다. 즉 비트 연산자를 사용해 덧셈을 구현하면 되는 문제이다.  간단하게 생각하면 비트 연산으로 더하기가 되려면 1과 0이 만나면 1이 되어야 하고 1과 1이 만나면 0, 0과 0이 만나도 0이 되어야 한다. XOR을 쓰면 정확하게 두 비트가 다른 경우에만 1이 되기 때문에 더하기 과정을 구현할 수는 있다. 그러나 단순하게 XOR 연산만 수행하다 보면 올림 처리된 즉 캐리가 발생하는 경우 캐리에 대한 처리가 이루어지지 않는다. //캐리가 발생하지 않는 덧셈1 + 2 = 01 ^ 10 = 11 = 3 -> 정상 값..

[NeetCode-LeetCode] Set Matrix Zeroes - Medium접근수학(?)풀이행렬에 0이 있는 위치의 행과 열 모든 숫자를 0으로 만드는 문제이다. 0이 있는 위치가 [3,4]이라면 3행에 있는 모든 숫자와 4열에 있는 모든 숫자를 0으로 만드는 것이다. 이 문제에 주어진 추가 질문으로는 O(mn)의 공간 복잡도로 푸는 건 대체적으로 좋지 않은 방법이고 개선하여 O(m+n)의 공간 복잡도로 풀 순 있지만 최선의 방법은 아니다 그렇다면 상수 공간 복잡도로 해결을 해보라는 말인데 상수 공간 복잡도로 해결하려면 추가적인 배열을 사용하지 않아야 한다는 소리다. public void setZeroes(int[][] matrix) { int m = matrix.length;..