kwang2134 님의 블로그

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

[Programmers] 전력망을 둘로 나누기 - LV 2접근완전 탐색풀이n 개의 송전탑이 트리 형태로 연결되어 있을 때 한 개의 연결을 끊어 나눠진 두 송전탑의 개수를 최대한 비슷하게 맞추는 문제이다. 두 송전탑의 개수의 차가 제일 작을 때 몇 개인지를 구해야 하므로 연결을 끊어 나눠진 두 트리에 있는 탑 개수를 세어 뺀 절댓값을 반환해야 한다.  트리를 표현하기 위한 방법이 배열을 사용한 방법과 List를 사용한 방법으로 풀었다. List로 푼 방법으로 설명을 하겠다. private static class Node { List connected; public Node() { this.connected = new ArrayList(); } ..

[Programmers] 베스트앨범 - LV 3접근해시풀이해시 카테고리의 문제로 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트앨범을 만드는 문제이다. 노래 수록 기준으로 속한 노래가 많이 재생된 장르를 먼저 찾는다. 가장 많이 재생된 장르라는 것은 해당 장르의 총 재생수를 기준으로 많은 순서대로 수록하게 된다. 장르 내에선 재생수를 기준으로 2 곡을 수록하게 되는데 횟수가 같다면 고유 번호가 낮은 노래를 먼저 수록하면 된다.  뭔가 SQL 문제로 나올만한 내용이긴 한데 해시 카테고리의 문제이고 대충 보면 HashMap을 써야 할 거 같다.  private static class Music { int index; int play; ..

[Programmers] 구명보트 - LV 2접근그리디투 포인터풀이무인도에 갇힌 사람들이 구명보트를 통해 탈출하는 문제로 구명보트에는 무게 제한이 있기 때문에 무게 제한을 만족하며 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 구하는 문제이다. 그런데 구명보트는 작기 때문에 한 번에 최대 2명씩 밖에 탈 수 없다.  2명, 2명이 한 보트당 최대 인원이다. 이 2명이라는 내용을 제대로 읽지 않아 불 필요하게 복잡한 코드와 함께 통과에 실패했다. 보트의 제한 무게가 40kg 이상 240kg 이하이기 때문에 무게만 맞춘다면 몇 사람이 타던 상관이 없는 줄 알고 풀었는데 보트에는 2명밖에 태울 수 없었다. 사실 너무 간단한 문제였다. public int solution(int[] people..