Computer >> 컴퓨터 >  >> 프로그래밍 >> Python

파이썬으로 배열에서 최대 너비 램프(Ramp) 찾기

문제 설명

배열 nums가 주어졌다고 가정해 보겠습니다. 여기서 램프(ramp)란 i < j이면서 nums[i] <= nums[j]를 만족하는 튜플 (i, j)를 의미하며, 이러한 램프의 너비는 (j - i)로 정의됩니다. 목표는 nums에서 최대 너비를 가진 램프를 찾는 것이고, 조건을 만족하는 램프가 존재하지 않는다면 0을 반환해야 합니다.

예를 들어 입력이 nums = [6,0,8,2,1,5]라면 결과는 4가 됩니다. 최대 너비의 램프는 (i, j) = (1, 5)에서 얻어지며, 이때 nums[1] = 0이고 nums[5] = 5이므로 너비는 5 - 1 = 4입니다.

해결 접근 방법

이 문제는 다음 단계를 따라 해결할 수 있습니다.

  • B := 새로운 맵(딕셔너리)을 생성합니다.

  • i를 0부터 nums의 크기까지 반복합니다.

    • x := nums[i]

    • x가 B에 이미 존재하면 B[x]의 끝에 i를 추가합니다.

    • 그렇지 않으면 B[x] := [i]로 초기화합니다.

  • mini := 처음에 무한대(inf) 하나를 담고 있는 리스트로 초기화합니다.

  • maxi := 처음에 음의 무한대(-inf) 하나를 담고 있는 리스트로 초기화합니다.

  • B의 모든 키를 오름차순으로 정렬한 순서대로 각 x에 대해 다음을 수행합니다.

    • mini의 마지막 원소와 B[x]의 최솟값 중 더 작은 값을 mini의 끝에 추가합니다.

  • B의 모든 키를 내림차순으로 정렬한 순서대로 각 x에 대해 다음을 수행합니다.

    • maxi의 마지막 원소와 B[x]의 최댓값 중 더 큰 값을 maxi의 끝에 추가합니다.

  • maxi를 뒤집은 뒤 마지막 원소를 제거합니다.

  • mini는 첫 번째 원소를 제거한 나머지 부분 배열로 설정합니다.

  • p := 0, res := -inf로 초기화합니다.

  • p가 mini의 크기보다 작은 동안 다음을 반복합니다.

    • res := res와 (maxi[p] - mini[p]) 중 더 큰 값

    • p := p + 1

  • res를 반환합니다.

동작 원리

이 알고리즘의 핵심은 각 값별로 등장한 인덱스를 맵에 저장한 뒤, 값이 작은 쪽에서의 누적 최소 인덱스(mini)와 값이 큰 쪽에서의 누적 최대 인덱스(maxi)를 미리 계산해 두는 것입니다. 정렬된 키 순서로 두 배열을 나란히 비교하면, 특정 값 기준으로 왼쪽 경계 후보와 오른쪽 경계 후보의 차이가 곧 그 구간에서 얻을 수 있는 최대 램프 너비가 됩니다. 전체 시간 복잡도는 정렬로 인해 O(n log n)입니다.

예제 구현

더 나은 이해를 위해 다음 파이썬 구현을 살펴보겠습니다.

def solve(nums):
    B = {}
    for i in range(len(nums)):
        x = nums[i]
        if x in B:
            B[x].append(i)
        else:
            B[x] = [i]

    mini = [float('inf')]
    maxi = [float('-inf')]
    for x in sorted(B.keys()):
        mini.append(min(mini[-1], min(B[x])))

    for x in sorted(B.keys(), reverse=True):
        maxi.append(max(maxi[-1], max(B[x])))

    maxi = maxi[::-1][:-1]
    mini = mini[1:]

    p = 0
    res = float('-inf')
    while p < len(mini):
        res = max(res, maxi[p] - mini[p])
        p += 1

    return res

nums = [6,0,8,2,1,5]
print(solve(nums))

입력

[6,0,8,2,1,5]

출력

4