[Java/Algorithm] Stack - 자판기에 넣은 지폐와 동전 반환하기

문제 설명

자판기는 아래와 같은 금액의 지폐와 동전을 투입받고 반환할 수 있다.

동전 종류: 10, 50, 100, 500
지폐 종류: 1000, 5000, 10000

투입한 지폐와 동전은 순서대로 정수 배열 arr에 주어진다.

사용자가 반환을 요청하면 자판기는 마지막으로 투입된 지폐 하나를 먼저 반환하고, 나머지 금액을 최소 개수의 동전으로 반환한다. 지폐는 한 번만 반환할 수 있고, 동전은 큰 금액부터 반환한다. 자판기에 동전은 반환할 만큼 충분한 수량이 있다고 가정한다.

예시

// 입력
int[] arr1 = {500, 1000, 50, 100, 5000};
// 출력
[5000, 500, 500, 500, 100, 50]
// 지폐는 마지막에 들어간 5000 하나만 반환
// 나머지는 모두 동전으로 반환해서 내림차순으로 정렬

풀이 방법

• 가장 마지막에 투입된 지폐를 먼저 반환한다
• 나머지 금액을 동전으로 최소 개수로 반환한다

이 두 가지 조건을 가지고 자판기에 투입된 금액을 반환하는 코드를 작성해야 하는 문제입니다. 가장 마지막에 들어간 것이 먼저 나온다는 제약 조건에서 후입선출 (LIFO)을 떠올려 스택 (Stack) 사용을 고려해볼 수 있습니다.

나머지 금액은 동전으로 반환하고 최소 개수로 반환해야 하므로, 가장 큰 금액의 동전으로 반환을 먼저 시도해야 최소 개수를 만족할 수 있습니다.

1. 마지막으로 넣은 지폐와 전체 투입 금액 계산하기
입력 배열을 돌면서 전체 투입한 금액의 합을 계산합니다. 더불어 1000, 5000, 10000으로 투입된 금액은 지폐를 넣었다는 뜻이므로, 조건문을 사용해 가장 마지막에 넣은 지폐의 액수를 확인합니다.

int lastBill = 0; // 마지막으로 넣은 지폐
int totalAmount = 0; // 총 투입된 금액
        
for (int value : arr) {
            if (value == 1000 || value == 5000 || value == 10000) {
                lastBill = value;
            }
            totalAmount += value;
        }

2. 마지막 지폐 먼저 반환하기
반환할 금액을 차례대로 추가할 ArrayList를 만들어 두었습니다. 투입한 금액 중 지폐가 있었는지 먼저 확인하고, 있다면 해당 마지막 지폐 금액을 리스트에 추가합니다. 지폐 하나를 반환한 나머지 금액은 모두 동전으로 반환해야하기 때문에, 총 금액에서 지폐 금액을 빼줍니다.

List<Integer> result = new ArrayList<>();

if (lastBill > 0) {
	result.add(lastBill);
    totalAmount -= lastBill;
}

3. 나머지 금액을 최소한의 동전으로 반환하기
동전을 최소 개수로 사용하려면 큰 금액의 동전부터 가능한 많이 사용한 후 작은 금액을 동전을 사용해야 합니다. 먼저, 동전의 크기를 내림차순으로 정렬한 배열을 만들어 둡니다. 남은 금액의 크기와 동전 금액을 비교하면서 최대한 큰 금액을 먼저 빼줍니다. 빼준 금액은 리스트에 차례대로 추가합니다.

int[] coins = {500, 100, 50, 10}; // 동전을 큰 금액 순서로 배열

for (int coin : coins) {
	while (totalAmount >= coin) {
    result.add(coin);
    totalAmount -= coin;
}

4. 리스트를 배열로 변환
반환 리스트를 완성한 후 문제의 요구사항에 맞게 숫자 배열로 변환합니다. 여기서는 스트림을 사용하고 있습니다.

int[] resultArr = result.stream().mapToInt(Integer::intValue).toArray();

스트림을 통해 리스트 컬렉션을 처리한 코드의 내용은 아래와 같습니다.

• result.stream(): 리스트를 스트림으로 변환합니다. result가 Integer 리스트기 때문에 Integer 객체의 스트림으로 변환되었습니다: (List<Integer> -> Stream<Integer>)
• mapToInt(): Stream<T> 인터페이스에서 제공하는 메소드입니다. 인자로 받은 매핑 함수에 따라서 스트림의 각 요소가 int 타입으로 변환되고, 변환된 int 값들을 intStream이라는 새로운 스트림에 담습니다: (Stream<Integer> -> IntStream)
  • Integer::intValue: 위 변환 작업 중간에 각 Integer 객체를 int로 바꾸는 역할을 수행합니다. 이렇게 작업 방법을 지정하는 함수를 매핑 함수라고 부릅니다. 스트림의 모든 Integer 객체를 intValue() 메소드를 호출해서 기본형 int로 변환합니다

과정을 정리하면,
1. List를 스트림으로 만들고
2. mapToInt()로 각 요소를 처리하겠다고 선언하는데
3. 처리하는 구체적인 방법을 Integer::intValue로 지정해서, Integer를 int로 바꿉니다
4. 그렇게 만들어진 int 값들을 모아서 새로운 스트림 형태인 IntStream을 만듭니다.
5. 마지막으로 이렇게 만들어진 스트림을 toArray() 배열로 변환합니다.

이렇게 원하는 형태의 값을 반환할 수 있게 됩니다.

최종 코드

import java.util.*;

class Solution {
    public int[] solution(int[] arr) {         
        int[] coins = {500, 100, 50, 10}; // 동전을 큰 금액 순서로 배열
        int lastBill = 0; // 마지막으로 넣은 지폐
        int totalAmount = 0; // 총 투입된 금액

        // 총 금액 계산 및 마지막 지폐 찾기
        for (int value : arr) {
            if (value == 1000 || value == 5000 || value == 10000) {
                lastBill = value;
            }
            totalAmount += value;
        }

        // 반환 리스트
        List<Integer> result = new ArrayList<>();

        // 마지막 지폐 반환
        if (lastBill > 0) {
            result.add(lastBill);
            totalAmount -= lastBill;
        }

        // 나머지 금액을 최소 동전 개수로 반환
        for (int coin : coins) {
            while (totalAmount >= coin) {
                result.add(coin);
                totalAmount -= coin;
            }
        }

        // 결과를 배열로 변환
        int[] resultArr = result.stream().mapToInt(Integer::intValue).toArray();
        return resultArr;
    }
}