파이썬으로 각 요소를 왼쪽 원소들의 최솟값으로 바꾸는 프로그램 구현하기

숫자로 이루어진 리스트 nums가 있다고 가정해 보겠습니다. 이때 각 nums[i]를 i의 왼쪽에 있는 요소들 중 가장 작은 값으로 교체해야 하며, 첫 번째 요소인 nums[0]은 0으로 대체합니다.

문제 예시

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

[15, 7, 9, 16, 12, 25]

출력은 아래와 같이 됩니다.

[0, 15, 7, 7, 7, 7]

출력 결과를 살펴보면, 인덱스 1부터는 해당 위치 왼쪽에 있는 값들 중 최솟값으로 바뀐 것을 확인할 수 있습니다. 인덱스 3 이후에는 왼쪽 원소 중 최솟값인 7이 반복되는 것을 볼 수 있습니다.

해결 접근 방법

이 문제는 한 번의 순회만으로 효율적으로 해결할 수 있습니다. 알고리즘 단계는 다음과 같습니다:

• 리스트 nums가 비어 있다면 빈 리스트를 반환합니다.
• 변수 j에 첫 번째 요소 nums[0]의 값을 저장합니다.
• nums[0]을 0으로 설정합니다.
• 인덱스 1부터 리스트 끝까지 반복하면서:
  • 현재 값을 임시 변수 k에 저장합니다.
  • nums[i]를 j(지금까지의 최솟값)로 교체합니다.
  • j와 k 중 더 작은 값으로 j를 갱신합니다.
• 변경된 리스트를 반환합니다.

이 방식은 각 위치에서 왼쪽 전체를 다시 탐색하지 않고, 지나온 값들의 최솟값만 유지하므로 시간 복잡도 O(n)으로 문제를 해결할 수 있습니다.

구현 코드

아래 코드를 통해 실제 동작을 확인해 보겠습니다.

class Solution:
    def solve(self, nums):
        if not nums:
            return []
        j = nums[0]
        nums[0] = 0
        for i in range(1, len(nums)):
            k = nums[i]
            nums[i] = j
            j = min(j, k)
        return nums

ob = Solution()
nums = [15, 7, 9, 16, 12, 25]
print(ob.solve(nums))

입력

[15, 7, 9, 16, 12, 25]

출력

[0, 15, 7, 7, 7, 7]

마무리

핵심 아이디어는 현재 위치보다 왼쪽에 있는 값들을 매번 처음부터 훑어보는 대신, 지금까지 등장한 값의 최솟값을 하나의 변수에 저장해 두는 것입니다. 덕분에 리스트를 한 번만 순회하면서도 정답을 구할 수 있으며, 입력 크기가 커져도 성능 저하 없이 동작합니다.