Find the Student that Will Replace the Chalk[M,Array,Binary Search,Simulation,Prefix Sum]

https://leetcode.com/problems/find-the-student-that-will-replace-the-chalk/description/?envType=daily-question&envId=2024-09-02

There are n students in a class numbered from 0 to n - 1. The teacher will give each student a problem starting with the student number 0, then the student number 1, and so on until the teacher reaches the student number n - 1. After that, the teacher will restart the process, starting with the student number 0 again.

You are given a 0-indexed integer array chalk and an integer k. There are initially k pieces of chalk. When the student number i is given a problem to solve, they will use chalk[i] pieces of chalk to solve that problem. However, if the current number of chalk pieces is strictly less than chalk[i], then the student number i will be asked to replace the chalk.

Return the index of the student that will replace the chalk pieces.

 

Example 1:

Input: chalk = [5,1,5], k = 22
Output: 0
Explanation: The students go in turns as follows:
- Student number 0 uses 5 chalk, so k = 17.
- Student number 1 uses 1 chalk, so k = 16.
- Student number 2 uses 5 chalk, so k = 11.
- Student number 0 uses 5 chalk, so k = 6.
- Student number 1 uses 1 chalk, so k = 5.
- Student number 2 uses 5 chalk, so k = 0.
Student number 0 does not have enough chalk, so they will have to replace it.

Example 2:

Input: chalk = [3,4,1,2], k = 25
Output: 1
Explanation: The students go in turns as follows:
- Student number 0 uses 3 chalk so k = 22.
- Student number 1 uses 4 chalk so k = 18.
- Student number 2 uses 1 chalk so k = 17.
- Student number 3 uses 2 chalk so k = 15.
- Student number 0 uses 3 chalk so k = 12.
- Student number 1 uses 4 chalk so k = 8.
- Student number 2 uses 1 chalk so k = 7.
- Student number 3 uses 2 chalk so k = 5.
- Student number 0 uses 3 chalk so k = 2.
Student number 1 does not have enough chalk, so they will have to replace it.

 

Constraints:

• chalk.length == n
• 1 <= n <= 105
• 1 <= chalk[i] <= 105
• 1 <= k <= 109

오랜만에 코딩하려니까 머리가 삐걱거린다.

백날 천날 유튭만 볼 게 아니라, 쉴 때도 이따금씩 코드를 좀 만져줘야겠다.

 

일단 워밍업인데 뭐라 뭐라 문제가 넘 길다;;

 

1. C

int chalkReplacer(int* chalk, int chalkSize, int k) {
    int j = 0;
    while(1){
        if(j==chalkSize) j=0;
        
        if(k < chalk[j]) return j;
        else{
            k = k - chalk[j];
            j++;
        }
    }
    return -1;
}

 

무난하게 위와 같이 코딩했더니 C인데도 time limint에 걸린다;;

제목에 괜히 BST가 있는 것이 아니구

 

int chalkReplacer(int* chalk, int chalkSize, int k) {
    int  j = 0;
    int sum = 0;
    while(1){
        if(j==chalkSize) j=0;
        sum += chalk[j];
        if(sum>k) return j;
        j++;
    }
    return -1;
}

 

반대로 해도 요상한 test case에 time limit이 걸린다.

 

해결법은 일단 chalk arrray의 토탈을 구하고 modular를 이용해 k값을 낮추는 것이다.

 

int chalkReplacer(int* chalk, int chalkSize, int k) {
    int  j = 0;
    long long total = 0;
    for(int i=0;i<chalkSize;i++){
        total += chalk[i];
    }
    k = k % total;
    int sum = 0;
    while(1){
        if(j==chalkSize) j=0;
        sum += chalk[j];
        if(sum>k) return j;
        j++;
    }
    return -1;
}

 

 

2. C++

subtract를 이용해서 풀어보기. C와 맥락은 같다.

class Solution {
public:
    int chalkReplacer(vector<int>& chalk, int k) {
        long long sum = 0;
        for(int i=0;i<chalk.size();i++){
            sum += chalk[i];
        }

        k %= sum;
        int ans = 0;
        for(int j=0;j<chalk.size();j++){
            k -= chalk[j];
            if(k<0) return j;
        }
        return -1;
    }
};

 

 

3. Python 축적방식 + Binary Search 사용

 

 

class Solution:
    def chalkReplacer(self, chalk: List[int], k: int) -> int:
        temp = [ 0 for _ in range(len(chalk))]
        temp[0] = chalk[0]
        for i in range(1,len(chalk)):
            temp[i] = temp[i-1] + chalk[i]
        
        k %= temp[-1]

        left = 0
        right = len(chalk)-1

        while left < right :
            mid = (left + right)//2
            if temp[mid] == k : return mid+1
            elif temp[mid] < k :
                left = mid+1
            else : right = mid

        return left

 

부등호 장난질을 좀 칠거면 아래처럼 하면 된다.

class Solution:
    def chalkReplacer(self, chalk: List[int], k: int) -> int:
        temp = [ 0 for _ in range(len(chalk))]
        temp[0] = chalk[0]
        for i in range(1,len(chalk)):
            temp[i] = temp[i-1] + chalk[i]
        
        k %= temp[-1]

        left = 0
        right = len(chalk)-1

        while left <= right :
            mid = (left + right)//2
            if temp[mid] == k : return mid+1
            elif temp[mid] < k :
                left = mid+1
            else : right = mid-1

        return left