가장 최근에 사용한 요소를 끝으로 이동하는 대기열을 설계하라는 요청을 받았다고 가정해 보겠습니다. 대기열은 1에서 n까지의 정수로 초기화됩니다. 이제 함수가 호출될 때마다 입력으로 지정된 위치에서 큐의 끝까지 값을 이동하도록 함수를 빌드해야 합니다. 함수를 여러 번 호출하고 함수는 이동 작업을 수행하는 동안 현재 큐 끝에 있는 값을 반환합니다.
따라서 대기열이 n =5 값으로 초기화되거나 1에서 5 사이의 값을 포함하는 경우. 이동이 수행되는 위치가 각각 5, 2, 3 및 1이면 출력은 5, 2, 4, 1
이 됩니다.이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- i :=배열 인덱스의 위치 - 1, 여기서 k 값은 정렬된 순서를 유지하는 오른쪽에 삽입될 수 있습니다.
- x :=데이터[i]에서 (k - 인덱스[i])번째 요소 삭제
- i+1 범위에서 인덱스 크기까지의 ii에 대해
- 인덱스[ii] :=인덱스[ii] - 1
- 데이터의 마지막 요소의 크기>=nn이면
- 목록 데이터 끝에 새 목록 삽입
- 목록 인덱스 끝에 n 삽입
- 데이터 끝에 x 삽입
- 데이터[i]가 rmpty이면
- 데이터에서 i번째 요소 삭제
- 인덱스에서 i번째 요소 삭제
- 반환 x
예
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
from bisect import bisect_right from math import sqrt class TestQueue: def __init__(self, n): self.n = n self.nn = int(sqrt(n)) self.data = [] self.index = [] for i in range(1, n+1): ii = (i-1)//self.nn if ii == len(self.data): self.data.append([]) self.index.append(i) self.data[-1].append(i) def solve(self, k): i = bisect_right(self.index, k)-1 x = self.data[i].pop(k - self.index[i]) for ii in range(i+1, len(self.index)): self.index[ii] -= 1 if len(self.data[-1]) >= self.nn: self.data.append([]) self.index.append(self.n) self.data[-1].append(x) if not self.data[i]: self.data.pop(i) self.index.pop(i) return x queue = TestQueue(5) print(queue.solve(5)) print(queue.solve(2)) print(queue.solve(3)) print(queue.solve(1))
입력
queue = TestQueue(5) print(queue.solve(5)) print(queue.solve(2)) print(queue.solve(3)) print(queue.solve(1))
출력
5 2 4 1