[프로그래머스][JAVA] Summer/Winter Coding(~2018) 예산

Summer/Winter Coding(~2018) 예산

https://school.programmers.co.kr/learn/courses/30/lessons/12982

프로그래머스

풀이 방법

한 기업 면접에서 봤던 라이브 코딩 테스트 문제이다.
분명 정렬하고 더하면서 하면 될 것 같은데 이상하게 안 풀려서 당황했던 문제이다. 긴장 + 처음 보는 라이브 코딩이라 당황해서 더 그랬던 것 같다.
당시에는 완전 탐색 + DP 라고 생각해서 배열을 정렬한 다음 재귀식으로 금액을 더해서 가장 큰 Count를 반환하도록 했는데 접근 방식은 좋았지만 너무 복잡하게 생각한 것 같다는 지적을 받았다.

집에 와서 다시 풀어보니 진짜 간단한 문제였다.
배열을 정렬한 다음 두 가지 경우의 수를 주의하면 쉽게 풀리는 문제이다.

1. 예산 책정이 불가능한 경우
2. 부서가 하나일 경우

1번의 경우는 아예 예산 지원이 불가능한 경우로 배열의 0번째 값이 예산을 초과하는 경우이다.
2번의 경우는 말 그대로 부서가 하나이면서 예산 지원이 가능한 경우이다. 이 땐 1을 반환해주면 된다.

이후로는 2중 반복문을 돌리면서 작은 금액부터 더해 그 값을 예산과 비교하고 초과하지 않는 선에서 count를 반환하면 쉽게 풀린다.

소스 코드

class Solution {
    public int solution(int[] d, int budget) {
        int answer = 0;
        
        // 오름차순 선택 정렬
        for(int i = 0; i < d.length; i++) {
            int min_i = i;
            for(int j = i + 1; j < d.length; j++) {
                if(d[j] < d[min_i])
                    min_i = j;
            }
            
            if(d[min_i] < d[i]) {
                int tmp = d[min_i];
                d[min_i] = d[i];
                d[i] = tmp;
            }
        }
        
        // 가장 첫 금액 먼저 검증
        if(budget < d[0]) {
            return answer;
        }
        else if(budget == d[0]) {
            return 1;
        }
        
        answer = 1;
        
        // 작은 금액부터 더하기
        for(int i = 1; i < d.length; i++) {
            int sum = d[0] + d[i];
            int count = 2;
            
            if(sum <= budget) {
                if(count > answer)
                    answer = count;
            }
            else if(sum > budget) {
                return 1;
            }
            
            for(int j = i + 1; j < d.length; j++) {
                sum += d[j];
                count++;
                
                if(sum == budget) {
                    if(count > answer)
                        answer = count;
                    break;
                }
                else if(sum > budget) {
                    sum -= d[j];
                    count--;
                    break;
                }
            }
            
            if(sum <= budget) {
                if(count > answer)
                    answer = count;
            }
        }
        
        return answer;
    }
}