[P&B] #38 PreCodingTest

프리코딩테스트 3-5

 

3) SelectRoom

오답 노트 코드

import java.util.stream.*;
import java.util.*;
class Solution {
    public int solution(int[][] A) {
        int dp[][] = A.clone();
        for (int i = 1; i < dp.length; i++) {
            dp[i][0] += dp[i - 1][0];
            dp[i][dp[i].length - 1] += dp[i - 1][dp[i - 1].length - 1];
        }
        for (int i = 0; i < dp.length; i++) {
            if (dp[i].length > 2) {
                for (int j = 1; j < dp[i].length - 1; j++) {
                    dp[i][j] = Math.min(dp[i][j] + dp[i - 1][j - 1], dp[i][j] + dp[i - 1][j]);
                }
            }
        }
        return Arrays.stream(dp[dp.length - 1]).min().getAsInt();
    }
}

 

문제 풀이 코멘트

최상단 및 최하단 열 계산: dp 배열의 첫 번째 열과 마지막 열의 값을 누적하여 계산합니다. 이렇게 함으로써 경로의 양 끝에서 시작하는 경우의 최소 대기 시간을 계산할 수 있습니다.

중간 열 계산: 위에서 계산한 값을 기반으로 중간 열의 값을 계산합니다. 각 방에 도달하는 최소 대기 시간을 계산하기 위해 현재 방의 시간과 바로 위 열의 왼쪽 방과 바로 위 열의 현재 방까지의 최소 대기 시간을 더한 값 중 최소 값을 선택합니다.

5) Vending Machine

오답 노트 코드

import java.util.*;
import java.util.stream.*;
class Solution {
    public int[] solution(int[] arr) {
        Arrays.sort(arr);
        List<Integer> result = new ArrayList<>();
        int[] coins = {500, 100, 50, 10};
        int keep = Arrays.stream(arr).sum(), idx = 0;
        if(arr[arr.length - 1] >= 1000) {
            result.add(arr[arr.length - 1]);
            keep -= arr[arr.length - 1];
        }
        while (idx < coins.length && keep >0) {
            if(keep >= coins[idx]) {
                result.add(coins[idx]);
                keep -= coins[idx];
            } else {
                idx++;
            }
        }
        return result.stream().mapToInt(i -> i).toArray();
    }
}

 

문제 풀이 코멘트

20점 만점에 16점을 받아 의문이었던 문제다. 코드는 다음과 같이 풀이된다.

1. 지폐 반환: 만약 입력된 금액 배열 중 가장 큰 값이 1000 이상인 경우, 해당 지폐를 먼저 반환하고, keep 변수에서 해당 금액을 차감합니다.
2. 동전 반환: coins 배열을 순회하면서 keep 변수가 0보다 크고 해당 동전을 반환할 수 있는 경우, 해당 동전을 result 리스트에 추가하고 keep 변수에서 해당 동전 금액을 차감합니다. 그렇지 않은 경우에는 다음 동전으로 넘어갑니다.

테스트케이스가 보여지지 않으니 비슷하게 풀었음에도 왜 감점 요소가 발생하는 지 알 수 없어 답답하다ㅜㅜ