kwang2134 님의 블로그

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

[Programmers] 피로도 - LV 2 접근완전 탐색풀이피로도가 주어지고 던전을 돌 때마다 던전이 요구하는 피로도가 소모된다. 던전에 입장하기 위한 최소 피로도가 존재할 때 가장 많은 던전을 탐험할 때 몇 개의 던전 탐험이 가능한지 구하는 문제이다. 그리디나 dp도 생각은 해봤는데 최소 피로도가 존재해 이전 선택이 다음 선택에 영향을 미치다 보니 그냥 완전탐색으로 풀었다.  private static int answer; public int solution(int k, int[][] dungeons) { answer = 0; boolean[] isVisited = new boolean[dungeons.length]; dfs(k, dungeons..

[Programmers] 더 맵게 - LV 2 접근힙풀이음식의 스코빌 지수가 주어지고 모든 음식의 스코빌 지수를 K 이상으로 만드는 문제이다. 음식을 섞어 스코빌 지수를 올릴 수 있고 음식을 몇 번 섞어야 모든 음식의 스코빌 지수가 K를 넘는지 구해야 한다. 힙 카테고리의 문제로 힙을 통해 구현된 우선순위 큐를 사용하면 간단하게 풀 수 있다. public int solution(int[] scoville, int K) { PriorityQueue pq = new PriorityQueue(); for (int i : scoville) { pq.offer(i); } int answer = 0; while (!pq.isEm..