이 문제에서는 walks와 target이라는 두 개의 리스트(값)가 주어집니다. 우리는 1차원 수직선 위의 위치 0에서 출발합니다. |walks[i]|는 실제로 걸은 걸음 수를 의미하며, walks[i]가 양수면 오른쪽으로, 음수면 왼쪽으로 이동했음을 나타냅니다. 걸을 때마다 한 블록씩 움직이므로, 현재 위치의 다음 정수 위치 또는 이전 정수 위치로 이동하게 됩니다.
우리가 구해야 하는 것은 최소 target번 이상 밟고 지나간 블록의 개수입니다.
예를 들어, 입력이 walks = [3, -7, 2]이고 target = 2라고 가정해 보겠습니다. 이 경우 출력은 5가 됩니다. 아래 그림에서 볼 수 있듯이 [0, 1], [1, 2], [2, 3], [-4, -3], [-3, -2] 구간이 각각 k = 2번 커버되기 때문입니다.
문제 해결 접근 방법
이 문제는 스위핑(sweeping) 기법을 활용해 효율적으로 해결할 수 있습니다. 각 구간의 시작점과 끝점에 변화량을 기록한 뒤, 위치 순서대로 누적하여 특정 레벨 이상 유지된 구간의 길이를 합산하는 방식입니다.
알고리즘 단계
- 현재 위치 pos := 0으로 초기화합니다.
- jumps라는 해시 맵(defaultdict)을 만들어, 키가 없을 때 기본값은 0이 되도록 합니다.
- walks의 각 dist에 대해 다음을 반복합니다:
- jumps[pos]에 dist > 0이면 +1, 아니면 -1을 더합니다.
- jumps[pos + dist]에 dist > 0이면 -1, 아니면 +1을 더합니다.
- pos := pos + dist로 현재 위치를 갱신합니다.
- lastpos := 0, level := 0, total := 0으로 초기화합니다.
- jumps의 키-값 쌍을 위치 기준으로 정렬하여 순회하면서:
- level >= target이면 total에 (pos - lastpos)를 더합니다.
- level에 val을 더하고, lastpos를 pos로 갱신합니다.
- total을 반환합니다.
예제 코드
아래 파이썬 구현을 통해 동작 방식을 더 잘 이해할 수 있습니다.
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
동작 원리 설명
이 알고리즘의 핵심은 각 걸음 구간을 시작점에서 +1, 끝점에서 -1로 표시하는 것입니다. 모든 지점을 정렬한 후 순차적으로 스캔하면, 어느 위치에서 몇 겹의 구간이 겹치는지(level)를 추적할 수 있습니다. level이 target 이상인 동안 이동한 거리를 모두 더하면, 정확히 target번 이상 밟힌 블록의 총 개수를 구할 수 있습니다.
이 방식은 각 걸음을 블록 단위로 하나하나 시뮬레이션하는 O(N×M) 방식보다 훨씬 효율적이며, 걸음 수가 많거나 이동 거리가 긴 경우에도 빠르게 동작합니다.