넘치게 채우기
[LeetCode] 1894. Find the Student that Will Replace the Chalk 본문
[LeetCode] 1894. Find the Student that Will Replace the Chalk
riveroverflow 2024. 9. 2. 09:26leetcode - 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
}
'PS > LeetCode' 카테고리의 다른 글
[LeetCode] 874. Walking Robot Simulation (0) | 2024.09.04 |
---|---|
[LeetCode] 1945. Sum of Digits of String After Convert (0) | 2024.09.03 |
[LeetCode] 2022. Convert 1D Array Into 2D Array (0) | 2024.09.01 |
[LeetCode] 2699. Modify Graph Edge Weights (0) | 2024.08.30 |
[LeetCode] 947. Most Stones Removed with Same Row or Column (0) | 2024.08.29 |