Walk와 target이라는 두 개의 목록이 있다고 가정합니다. 처음에 우리는 1차원 선에서 위치 0에 있습니다. 지금 |걷다[i]| 걸은 걸음 수를 나타냅니다. 그리고 walk[i]가 양수이면 오른쪽으로 걸었다는 것을 나타내고 왼쪽에는 음수를 나타냅니다. 걸을 때 한 블록, 즉 다음 또는 이전 정수 위치를 이동합니다. 목표 횟수 이상으로 걸어간 블록의 수를 찾아야 합니다.
따라서 입력이 walks =[3, -7, 2] target =2와 같으면 출력은 5가 됩니다. 다음 그림에서 [0, 1], [1, 2], [2 , 3], [-4, -3], [-3, -2]는 k =2회 적용됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- 위치 :=0
- jumps :=키가 없을 때 기본값은 0인 해시 맵
- 산책의 각 dist에 대해 다음을 수행합니다.
- jumps[pos] :=jumps[pos] + dist인 경우 1> 그렇지 않은 경우 -1
- jumps[pos + dist] :=jumps[pos + dist] - dist일 경우 1> 그렇지 않으면 -1
- pos :=pos + dist
- 마지막 위치 :=0
- 레벨:=0
- 총계:=0
- 각 위치 pos 및 점프의 정렬된 키-값 쌍의 값 val에 대해 do
- 수준>=대상이면
- total :=total + pos - lastpos
- 레벨 :=레벨 + 발
- lastpos :=pos
- 수준>=대상이면
- 총 수익
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
from collections import defaultdict def solve(walks, target): pos = 0 jumps = defaultdict(int) for dist in walks: jumps[pos] += 1 if dist > 0 else -1 jumps[pos + dist] -= 1 if dist > 0 else -1 pos += dist lastpos = level = total = 0 for pos, val in sorted(jumps.items()): if level >= target: total += pos - lastpos level += val lastpos = pos return total walks = [3, -7, 2] target = 2 print(solve(walks, target))
입력
[3, -7, 2], 2
출력
5