X가 대기열의 모든 사람에게 변경 사항을 줄 수 있는지 확인

난이도 중급
자주 묻는 질문 아마존
조회수 16

문제 정책

X는 아이스크림 판매자이고 n 명의 사람들이 변발 아이스크림을 사기 위해. Arr [i]는 대기열에있는 사람의 액면가를 나타냅니다. 가능한 액면가는 5, 10, 20입니다. X의 초기 잔액이 0이고 아이스크림 가격이 5 인 경우 X 여부를 결정합니다. 줄에 서있는 모든 사람들에게 잔돈을 줄 수 있을까요? 따라서 문제는 "X가 대기열의 모든 사람에게 변경을 줄 수 있는지 확인"입니다.

X가 대기열의 모든 사람에게 변경 사항을 줄 수 있는지 확인

arr[] = {5, 5, 10, 20}
true
arr[] = {10, 5, 5, 5, 5, 5}
false
arr[] = {5, 5, 5, 20, 5, 10}
true

X가 대기열의 모든 사람에게 변경을 줄 수 있는지 확인하는 알고리즘

생각

아이디어는 X가 가지고있는 5, 10, 20의 교단을 추적하는 것입니다. 이것들을 count5, count10, count20으로 표현하자. 가능한 한 높은 가치의 통화로 잔돈을 반환하는 것이 항상 최적입니다. 총 XNUMX 건이 있는데

  • arr [i] = 5,
    count5를 1 씩 증가
  • arr [i] = 10,
    count5> 0이면 count10을 1 씩 증가시키고 count5를 1 씩 감소시킵니다.
  • arr [i] = 20,
    count10> 0이고 count5> 0이면 count20을 1 씩 증가시키고 count10과 count5를 1 씩 감소시킵니다.
    그렇지 않으면 count5> 2이면 count20을 1 씩 증가시키고 count5를 3 씩 감소시킵니다.

접근

  1. 세 변수 count5, count10 및 count20을 0으로 초기화합니다.
  2. 주어진 횡단 정렬.
  3. arr [i]가 5이면 count5를 1 씩 증가시킵니다.
  4. 그렇지 않으면 arr [i]가 10이면 count5> 0인지 확인하고, 그렇다면 count10을 1 씩 증가시키고 count5를 1 씩 감소시킵니다. 그렇지 않으면 X가 모든 고객에게 변경 사항을 줄 수 없으면 false를 반환합니다.
  5. 그렇지 않으면 arr [i]가 20이면 count10이 0보다 크고 count5가 0보다 큰지 확인합니다. 그렇다면 count20을 1 씩 늘리고 count5와 count10을 하나씩 줄입니다. 그렇지 않으면 count5가 2보다 큰지 확인합니다. 예, count20을 1 씩 늘리고 count5를 3 씩 줄입니다. 그렇지 않으면 X가 모든 고객에게 변경 사항을 제공 할 수 없으며 false를 반환합니다.
  6. X가 모든 고객에게 변경 사항을 반환 할 수 있으면 true를 반환합니다.

암호

X가 대기열의 모든 사람에게 변경을 줄 수 있는지 확인하는 Java 코드

class CheckIfXCanGiveChangeToEveryPersonStandingInQueue {
    private static boolean checkIfPossible(int[] arr) {
        // initialize count0, counnt10 and count20 as 0
        int count5 = 0, count10 = 0, count20 = 0;
        
        // traverse in the array
        for (int i = 0; i < arr.length; i++) {
            // Case 1 : arr[i] = 5
            if (arr[i] == 5) {
                // increment count5 by 1
                count5++;
            }
            // Case 2 : arr[i] = 10
            else if (arr[i] == 10) {
                // if there are some 5 rs coins return 1
                if (count5 > 0) {
                    // decrement count5 by 1 and increment count10 by 1
                    count5--;
                    count10++;
                } else {
                    // if there are not, X cannot give change to everyone
                    return false;
                }
            }
            // Case 3 : arr[i] = 20
            else {
                // if there are some 10 rs coins and some 5 rs coin return one one each
                if (count10 > 0 && count5 > 0) {
                    count10--;
                    count5--;
                    count20++;
                } else if (count5 > 2) {
                    // else if there are 3 or more 5 rs coins return 3
                    count5 -= 3;
                    count20++;
                } else {
                    // X cannot give chnage to everyone
                    return false;
                }
            }
        }

        // X can give change to everyone
        return true;
    }

    public static void main(String[] args) {
        // Example 1
        int arr1[] = new int[]{5, 5, 10, 20};
        System.out.println(checkIfPossible(arr1));

        // Example 2
        int arr2[] = new int[] {10, 5, 5, 5, 5, 5};
        System.out.println(checkIfPossible(arr2));

        // Example 3
        int arr3[] = new int[]{5, 5, 5, 20, 5, 10};
        System.out.println(checkIfPossible(arr3));
    }
}
true
false
true

X가 큐의 모든 사람에게 변경을 줄 수 있는지 확인하는 C ++ 코드

#include<bits/stdc++.h> 
using namespace std; 

bool checkIfPossible(int *arr, int n) {
    // initialize count0, count10 and count20 as 0
    int count5 = 0, count10 = 0, count20 = 0;

    // traverse in the array
    for (int i = 0; i < n; i++) {
        // Case 1 : arr[i] = 5
        if (arr[i] == 5) {
            // increment count5 by 1
            count5++;
        }
        // Case 2 : arr[i] = 10
        else if (arr[i] == 10) {
            // if there are some 5 rs coins return 1
            if (count5 > 0) {
                // decrement count5 by 1 and increment count10 by 1
                count5--;
                count10++;
            } else {
                // if there are not, X cannot give change to everyone
                return false;
            }
        }
        // Case 3 : arr[i] = 20
        else {
            // if there are some 10 rs coins and some 5 rs coin return one one each
            if (count10 > 0 && count5 > 0) {
                count10--;
                count5--;
                count20++;
            } else if (count5 > 2) {
                // else if there are 3 or more 5 rs coins return 3
                count5 -= 3;
                count20++;
            } else {
                // X cannot give chnage to everyone
                return false;
            }
        }
    }

    // X can give change to everyone
    return true;
}

int main() {
    // Example 1
    int arr1[] = {5, 5, 10, 20};
    if (checkIfPossible(arr1, sizeof(arr1) / sizeof(arr1[0]))) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }

    // Example 2
    int arr2[] = {10, 5, 5, 5, 5, 5};
    if (checkIfPossible(arr2, sizeof(arr2) / sizeof(arr2[0]))) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }

    // Example 3
    int arr3[] = {5, 5, 5, 20, 5, 10};
    if (checkIfPossible(arr3, sizeof(arr3) / sizeof(arr3[0]))) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
}
true
false
true

복잡성 분석

시간 복잡성 

의 위에), n 개의 요소가있는 입력 배열을 순회했기 때문입니다. 그리고 이것은 알고리즘이 선형 시간으로 실행되도록했습니다.

공간 복잡성

O (1), 배열을 사용하지 않았기 때문입니다. 우리는 일정한 공간을 차지하는 donly 3 개의 변수를 사용했습니다. 따라서 일정한 공간 복잡성.
여기서 n은 총 고객 수입니다.

Translate »