n개의 숫자가 있는 배열 A와 또 다른 입력 K가 있다고 가정하면 주어진 작업을 수행한 후 마지막으로 0으로 줄어들 인덱스를 찾아야 합니다. 작업은 다음과 같이 설명됩니다 -
A[0]에서 시작하여 A[N – 1]까지 각 요소를 A[i] =A[i] – K로 업데이트합니다. 이제 A[i]
모든 요소가 0이 될 때까지 작업을 반복해야 합니다. 그리고 마지막으로 0이 될 인덱스를 반환합니다.
따라서 입력이 A =[4, 3, 6, 8, 3, 10] 및 K =4 와 같으면 출력은 5가 됩니다. 연산 1 − A ={0, 0, 2 , 4, 0, 6} 연산 2 − A ={0, 0, 0, 0, 0, 2} 연산 3 − A ={0,0, 0, 0, 0, 0}
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
n :=A의 크기
-
idx :=-1
-
0에서 n 사이의 i에 대해 수행
-
A[i] :=(A[i] + k - 1) / k
-
-
0에서 n 사이의 i에 대해 수행
-
A[i]>=x이면
-
x :=A[i]
-
idx :=나는
-
-
-
IDx를 반환
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
def search_index(A, k): n = len(A) idx = -1 x = -10**9 for i in range(n): A[i] = (A[i] + k - 1) // k for i in range(n): if (A[i] >= x): x = A[i] idx = i return idx arr = [4, 3, 6, 8, 3, 10] K = 4 print(search_index(arr, K))
입력
[4, 3, 6, 8, 3, 10], 4
출력
5