분필을 대신할 학생 찾기

1894. 분필을 대신할 학생을 찾아보세요

난이도:중

주제: 배열, 이진 검색, 시뮬레이션, 접두사 합

0부터 n - 1까지 번호가 매겨진 학급에는 n명의 학생이 있습니다. 교사는 학생 번호 0부터 시작하여 학생 번호 1, 이런 식으로 학생 번호 n에 도달할 때까지 각 학생에게 문제를 줍니다. - 1. 그 후, 교사는 다시 학생 번호 0부터 시작하여 프로세스를 다시 시작합니다.

인덱스가 0인 정수 배열 분필과 정수 k가 주어졌습니다. 처음에는 k개의 분필 조각이 있습니다. i번 학생에게 해결해야 할 문제가 주어지면, 그들은 그 문제를 해결하기 위해 분필[i] 분필 조각을 사용할 것입니다. 그러나 현재 분필 조각 수가 분필[i]보다 완전히 적다면 학생 번호 i에게 분필을 교체하라는 메시지가 표시됩니다.

분필 조각을 교체할 학생의 색인을 반환합니다.

예 1:

• 입력: 분필 = [5,1,5], k = 22
• 출력: 0
• 설명: 학생들은 다음과 같이 차례로 입장합니다.
  • 0번 학생은 분필 5개를 사용하므로 k = 17입니다.
  • 1번 학생은 분필 1개를 사용하므로 k = 16입니다.
  • 2번 학생은 분필 5개를 사용하므로 k = 11입니다.
  • 0번 학생은 분필 5개를 사용하므로 k=6입니다.
  • 1번 학생은 분필 1개를 사용하므로 k=5입니다.
  • 2번 학생은 분필 5개를 사용하므로 k = 0입니다.
  • 0번 학생은 분필이 부족해서 분필을 교체해야 합니다.

예 2:

• 입력: 분필 = [3,4,1,2], k = 25
• 출력: 1
• 설명: 학생들은 다음과 같이 차례로 입장합니다.
  • 0번 학생은 분필 3개를 사용하므로 k = 22.
  • 1번 학생은 분필 4개를 사용하므로 k = 18.
  • 2번 학생은 분필 1개를 사용하므로 k = 17.
  • 3번 학생은 분필 2개를 사용하므로 k = 15.
  • 0번 학생은 분필 3개를 사용하므로 k = 12.
  • 1번 학생은 분필 4개를 사용하므로 k = 8.
  • 2번 학생은 분필 1개를 사용하므로 k = 7.
  • 3번 학생은 분필 2개를 사용하므로 k = 5.
  • 0번 학생은 분필 3개를 사용하므로 k = 2.
  • 1번 학생은 분필이 부족해서 분필을 교체해야 합니다.

제약조건:

• chalk.length == n
• 1 5
• 1 5
• 1 9

힌트:

1. k가 분필의 합보다 작아질 때까지 k에서 분필의 합을 뺍니다.
2. 이제 배열을 반복합니다. chalk[i]가 k보다 작으면 이것이 답입니다. 그렇지 않으면 k에서 chalk[i]를 빼고 계속하세요.

해결책:

문제를 단계별로 분석해 보겠습니다.

접근하다:

1. 총 분필 소비량:
   먼저, 한 라운드(학생 0부터 학생 n-1까지)에 필요한 분필의 총량을 계산합니다. 이는 k개의 분필 조각으로 얼마나 많은 완전한 라운드를 덮을 수 있는지 고려하여 k 값을 줄이는 데 도움이 됩니다.

2. k를 모듈로 줄이기:
   k가 한 라운드를 완료하는 데 필요한 총 분필보다 큰 경우 k % total_chalk를 사용하여 문제를 단순화할 수 있습니다. 이 작업을 수행하면 최대한 많은 라운드를 수행한 후 남은 초크가 제공되므로 해결해야 할 문제가 더 작아집니다.

3. 분필이 부족한 학생 찾기:
   k가 현재 학생의 분필 요구 사항보다 작아질 때까지 각 학생의 분필 소비량을 반복하여 k에서 뺍니다. 이 학생의 지수가 우리의 답입니다.

예제 연습:

분필 = [3, 4, 1, 2] 및 k = 25를 예로 들어보겠습니다.

1. 총 분필 소비량:

   text{total_chalk} = 3 + 4 + 1 + 2 = 10

1. k 줄이기:

   k % 10 = 25 % 10 = 5

이제 가능한 한 많은 라운드를 뺀 후 k = 5가 됩니다.

1. 학생 찾기:
   • 학생 0은 분필 3개를 사용하므로 k = 5 - 3 = 2.
   • 학생 1에게는 분필 4개가 필요하지만 k = 2이므로 4보다 작습니다.
   • 그러므로 분필을 교체해야 할 사람은 학생 1이 됩니다.

이 솔루션을 PHP로 구현해 보겠습니다: 1894. 분필을 대신할 학생을 찾아보세요

<?php
/**
 * @param Integer[] $chalk
 * @param Integer $k
 * @return Integer
 */
function chalkReplacer($chalk, $k) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:

//Example 1
$chalk = [5,1,5];
$k = 22;
echo chalkReplacer($chalk, $k);  // Output: 0

//Example 2
$chalk = [3, 4, 1, 2];
$k = 25;
echo chalkReplacer($chalk, $k);  // Output: 1
?>

Explanation:

1. Total Chalk Sum: We sum up all the chalk requirements to get the total for one complete round.
2. Modulo Operation: Using modulo with k, we get the effective number of chalks to distribute after full rounds.
3. Find the Student: We then iterate through the students, checking if the remaining chalk is sufficient. The first time it's insufficient, that student's index is the answer.

Complexity:

• Time Complexity: O(n) — we sum the array and then iterate through it once.
• Space Complexity: O(1) — only a few variables are used, independent of the input size.

This approach ensures that the problem is solved efficiently even for large inputs.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks ?. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

• LinkedIn
• GitHub

위 내용은 분필을 대신할 학생 찾기의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!