이코테 - 공유기 설치 with JAVA
해결 이 문제를 해결하기 위해서는 공유기 설치 간격을 이분탐색으로 구하면 된다. 즉, 공유기 설치 간격을 정해서 입력받은 공유기의 수보다 공유기를 설치 못한다면 공유기 설치 간격을 줄이고 반대로, 입력받은 공유기 수와 같거나 더 많이 설치 가능하다면 공유기 설치 간격을 늘려가며 이분탐색을 진행한다. 예를 들어, 집은 1, 2, 4, 8, 9 에 위치하고 공유기는 3개를 설치하고 싶다고 가정하자. 집간 최소 간격은 1이고 최대 간격은 8이다. 따라서 start=1, end=8로 설정한다. 첫번째 mid= 4가 되고 이는 공유기 설치 간격은 4가 되는 것이다. 위 집들에 적용하면 1, 8에 설치 가능하다. 이는 공유기 3개보다 적으므로 설치 간격을 줄인다. 두번째로는 start=1, mid=2, end=3 ..
Programmers - 무지의 먹방 라이브 with JAVA
로직 우선, 큐에 [음식 양, 음식 번호] 를 넣고 음식양이 오름차순이 되도록 정렬한다. 예를 들어, [1, 2], [2, 3], [3, 1]이 있다고 가정하자. - 처음 꺼낸 리스트는 [1, 2]가 된다. - 음식양 1을 전체 리스트의 길이(3)만큼 먹는다. 하지만 1*3은 k보다 작으므로 더 진행 - 두번째 꺼낸 리스트는 [2, 3]이 된다. - 전에 1만큼 먹었기 때문에 2-1 = 1이 된다. - 음식양 1을 전체 리스트의 길이(2)만큼 먹는다. 그럼 지금까지 3 + 2를 먹었다. 이는 k와 같으므로 리스트를 다시 넣어주고 종료한다. (지금까지 먹은양이 k보다 크다는 의미는 이번 음식이 없어지면서 또는 없어지기 전에 k만큼 먹었다고 할 수 있다.) 종료 시점에 리스트의 번호만 보면 [1, 3]이 남..
이코테 - 만들 수 없는 금액 with JAVA
문제 N개의 동전으로 만들 수없는 양의 정수 중 최솟값을 구하라 로직 예를 들어, [1, 1, 2, 3, 9] 원이 있다고 가정하자. 1. 1원을 가지고는 1원까지 만들 수 있다. 2. 1원을 가지고는 2원까지 만들 수 있다. 3. 2원을 가지고는 4원까지 만들 수 있다. 4. 3원을 가지고는 7원까지 만들 수 있다. 5. 9원을 가지고는 16원까지 만들 수 있다. 증명 1원 - 1 2원 - 1, 1 3원 - 1, 2 4원 - 1, 1, 2 5원 - 3, 2 6원 - 3, 2, 1 즉, 결론적으로 a원을 가지고 있다면 기존에 만들 수 있는 금액 m원에 더해 a+m원까지 만들 수 있다. 코드 import java.util.*; public class Q4 { public static void main(St..
Programmers - 블록 이동하기 with JAVA
로직 이 문제는 너무 복잡했다. 따라서 차분히 설계 후 코드를 작성하는 것이 훨씬 도움이 많이 됨을 느꼈다. 기본적으로 우선순위 큐와 방문처리 배열을 활용해 로직을 처리한다. - 우선 순위 큐에은 비용, (x1, y1), (x2, y2), 방향을 담는다. - 방문처리는 가로, 세로 둘 다 (x2, y2)를 기준으로 방문처리를 한다. - 항상 가로는 왼쪽, 세로는 위쪽이 (x1, y1)이 되도록 고정 처리한다. - 방향마다 모든 이동 경로에 대한 로직을 작성한다. 코드 import java.util.*; class Solution { public int solution(int[][] board) { int n = board.length; int m = board[0].length; // 비용, x1, y1..
