C++로 제거해야 할 상자 개수 구하기

문제 소개

이 문제에서는 각 요소가 상자 더미(높이 1짜리 상자들이 쌓인 형태)를 나타내는 배열 arr[]가 주어집니다. 우리의 목표는 제거해야 할 상자의 총 개수를 구하는 것입니다.

사람은 배열의 인덱스 0에 해당하는 상자 더미 위에 서 있으며, 배열의 끝까지 이동해야 합니다. 한 더미에서 다음 더미로 이동하는 유일한 방법은 바로 옆 더미로 점프하는 것입니다.

점프는 다음 더미의 높이가 현재 높이와 같거나 더 낮을 때만 가능합니다. 만약 다음 더미가 더 높다면, 두 높이가 같아질 때까지 다음 더미에서 상자를 제거해야 합니다. 즉, 첫 번째 더미에서 마지막 더미까지 이동하는 동안 제거해야 하는 상자의 총 개수를 구하는 것이 우리의 과제입니다.

예시로 이해하기

입력 : arr[] = {5, 7, 3, 1, 2}
출력 : 3

풀이 설명

처음에 사람은 높이 5에 서 있습니다.

1단계 − 높이 7인 두 번째 위치로 이동하려면 2개의 상자를 제거해야 합니다.

2단계 − 높이 3인 세 번째 위치로 이동할 때는 상자를 제거할 필요가 없습니다.

3단계 − 높이 1인 네 번째 위치로 이동할 때도 상자를 제거하지 않습니다.

4단계 − 높이 2인 다섯 번째 위치로 이동할 때는 1개의 상자를 제거합니다. 따라서 제거된 상자의 총 개수는 3개가 됩니다.

해결 접근 방법

이 문제의 가장 간단한 해결 방법은 배열을 처음부터 끝까지 순회하면서 다음 요소가 현재 요소보다 큰지 확인하는 것입니다. 만약 다음 요소가 더 크다면, 두 값의 차이를 제거해야 할 상자의 총 개수를 저장하는 boxesRemoved 변수에 누적합니다. 모든 순회가 끝나면 최종적으로 boxesRemoved 값을 반환하면 됩니다.

구현 예제

아래는 위 해결 방법의 동작을 보여주는 C++ 프로그램입니다.

#include <iostream>
using namespace std;
int findBoxesRemoved(int arr[], int n){
    int boxesRemoved = 0;
    for (int i = 0; i < n-1; i++) {
       if (arr[i] < arr[i+1])
           boxesRemoved += (arr[i+1] - arr[i]);
   }
    return boxesRemoved;
}
int main(){
    int arr[] = { 5, 7, 3 , 1, 2, 6 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<"끝까지 이동하기 위해 제거해야 할 상자의 총 개수는 "<<findBoxesRemoved(arr, n);
    return 0;
}

실행 결과

끝까지 이동하기 위해 제거해야 할 상자의 총 개수는 7

이 알고리즘은 배열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 추가 메모리 사용 없이 O(1) 공간 복잡도로 효율적으로 동작합니다.