kwang2134 님의 블로그

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

[Programmers] 프로세스 - LV 2 접근큐풀이프로세스를 우선순위에 맞춰 실행하였을 경우 특정 위치의 프로세스가 몇 번째에 실행되는지 구하는 문제이다. 스택과 큐 파트에 있는 문제인데 설명부터 실행 대기 큐에 존재하는 프로세스로부터 수행되기 때문에 큐를 사용하는 문제이다. 큐에서 꺼낸 프로세스보다 우선순위가 높은 프로세스가 큐에 존재하는 경우 프로세스를 다시 큐에 넣게 되고 한 번 실행한 프로세스는 그대로 종료된다. 큐에 특정 위치의 프로세스가 몇 번째 실행되는지 구해야 하는 문제이기 때문에 우선순위와 위치를 같이 관리해주어야 한다. private class Process { int location; int priority; public Process(..

[Programmers] 의상 - LV 2 접근해시풀이의상을 조합해 만들 수 있는 모든 경우의 수를 구하는 문제이다. 의상의 카테고리에서 최대 1개의 의상을 입을 수 매일 최소 1개의 의상은 필수로 입어야 한다.  public int solution(String[][] clothes) { Map clothesMap = new HashMap(); for (String[] clothe : clothes) { clothesMap.merge(clothe[1], 1, Integer::sum); } int answer = 1; for (int count : clothesMap.values()) { answer..