[LeetCode] 1894. Find the Student that Will Replace the Chalk

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

leetcode - Find the Student that Will Replace the Chalk

문제 유형 : 그리디, 수학

문제 난이도 : Medium

 

문제

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.

 

n명의 학생이 0부터 n-1번으로 지정되어있다.

교사는 학생들에게 문제풀이를 시키는데, 0번학생부터 순차적으로 진행한다.

n-1번 학생이 끝나면, 다시 0번학생부터 한다.

 

정수 배열 chalk와 정수 k를 받는다. k조각만큼 분필이 있고, i번째 학생은 문제를 풀 때 마다 chalk[i]개만큼의 분필을 사용한다.

만약 chalk[i]보다 남은 분필이 적다면, i번째 학생이 분필을 다시 채워야 한다.

분필을 다시 가져올 학생의 번호를 구하시오.

 

풀이

무식하게 루프를 k가 chalk[i]보다 작아질 때 까지 돌리면 시간이 오래 걸린다.

대신, 확실하게 사이클을 도는 만큼 분필 숫자를 나눈 나머지를 이용하면 된다.

예를 들어서, chalk가 [1,2,3,4]라면, 한 바퀴 도는데 10개를 소모하므로, k %= 10을 해주고 배열을 한 번만 순회하면 되는 것이다.

 

배열을 순회하면서, chalk[i]가 k보다 크다면 k에서 chalk[i]만큼 빼주면 되고, 아니면 i를 반환하면 된다.

 

코드

C++

class Solution {
public:
    int chalkReplacer(vector<int>& chalk, int k) {
        long long total = 0;
        for(const auto &x : chalk) {
            total += x;
        }
        k %= total;

        for(int i = 0; i < chalk.size(); i++) {
            if(chalk[i] <= k) k -= chalk[i];
            else return i;
        }

        return 0;
    }
};

 

GO

func chalkReplacer(chalk []int, k int) int {
    var total int64

    for _, c := range chalk {
        total += int64(c)
    }
    k = int(int64(k) % total)

    for i, v := range chalk {
        if v > k {
            return i
        }
        k -= v
    }
    return 0
}