파이썬으로 자동차 속도가 일정하게 유지된 가장 긴 부분 리스트 찾는 방법

시간 간격이 동일하게 떨어진 시점에서 자동차의 위치를 나타내는 숫자 리스트가 있다고 가정해 보겠습니다. 이때 자동차가 일정한 속도(등속)로 주행한 가장 긴 부분 리스트(sublist)의 크기를 구하는 것이 목표입니다.

예를 들어 입력이 다음과 같다면,

positions = [0, 4, 8, 12, 6, 4, 0]

부분 리스트 [0, 4, 8, 12]에서 인접한 위치 사이의 거리가 모두 4로 일정하므로, 결과는 4가 됩니다.

해결 접근 방식

이 문제는 리스트를 한 번만 순회하면서 인접한 두 위치 사이의 거리가 이전 구간의 거리와 같은지 비교하는 방식으로 해결할 수 있습니다. 알고리즘의 핵심 단계는 다음과 같습니다.

• 순회 시작 인덱스 j := 1로 초기화합니다.
• 최대 개수 max_cnt := 0, 현재 연속 개수 current := 0으로 초기화합니다.
• 첫 번째 구간의 거리를 distance := |positions[0] − positions[1]|로 설정합니다.
• j가 리스트 크기보다 작은 동안 다음을 반복합니다.
  • prev := positions[j − 1]로 이전 위치를 저장합니다.
  • distance와 |positions[j] − prev|가 같으면 current를 1 증가시킵니다.
  • 같지 않으면 max_cnt를 갱신하고, current를 1로 초기화한 뒤 distance를 새로운 구간 거리로 변경합니다.
  • 매 반복마다 max_cnt := max(max_cnt, current)로 최댓값을 갱신하고, j를 1 증가시킵니다.
• 마지막에 max_cnt + 1을 반환합니다. (구간 수 + 1 = 요소 개수이기 때문입니다.)

파이썬 구현 예제

아래 코드를 통해 더 쉽게 이해할 수 있습니다.

class Solution:
    def solve(self, positions):
        j = 1
        max_cnt = 0
        current = 0
        distance = abs(positions[0] - positions[1])
        while j < len(positions):
            prev = positions[j - 1]
            if distance == abs(positions[j] - prev):
                current += 1

            else:
                max_cnt = max(max_cnt, current)
                current = 1
                distance = abs(positions[j] - prev)
            max_cnt = max(max_cnt, current)
            j += 1
        return max_cnt + 1

ob = Solution()
positions = [0, 4, 8, 12, 6, 4, 0]
print(ob.solve(positions))

입력

[0, 4, 8, 12, 6, 4, 0]

출력

4

복잡도 분석

이 알고리즘은 리스트 전체를 한 번만 순회하므로 시간 복잡도는 O(n)이며, 몇 개의 변수만 사용하므로 공간 복잡도는 O(1)입니다. 따라서 매우 긴 위치 데이터에도 효율적으로 동작합니다.