문제

연속된 블록들의 높이가 주어집니다. (ex. [1, 5, 5, 2, 6])
두 사람은 같은 블록에서 시작을 하고, 블록을 이동하여 최대한 멀리 떨어지려고 합니다.
이 때 블록의 이동은, 현재 블록보다 이동하려는 블록의 높이가 같거나 높은 곳으로 밖에 이동하지 못 합니다. (예를 들어서 1에서 시작하면 두 번째 5까지 밖에 가지 못함)

두 사람이 떨어질 수 있는 거리 중 최대의 거리를 구하세요.

제한 사항

• 블록의 수는 2 이상 20만 이하입니다.
• blocks의 각 원소들은 1 이상 10억 이하입니다.

예시

• blocks = [1, 5, 5, 2, 6]일 때, 두 사람이 모두 2에서 각자 왼쪽, 오른쪽으로 점프를 해 나갈 때 거리가 가장 멀어집니다.
• blocks = [2, 6, 8, 5]일 때, 두 사람이 가장 멀어질 때는 한 사람이 2, 다른 사람이 8에 있을 때 가장 멀어집니다.

풀이

시간초과 아이디어

• 이 문제를 풀기 위해서 가장 최적의 위치부터 먼저 찾아야겠다는 생각으로 enumerate(blocks)를 (높이, 인덱스) 순으로 해서 정렬한 배열을 새로 만들었다. (왜냐하면 높이가 낮은 순부터 찾아야 점프할 수 있는 블록이 많아지기 때문)
• 어떤 블록에서 시작한다고 쳤을 때, 왼쪽 사람이 어디까지 왼쪽으로 점프할 수 있는지, 오른쪽 사람은 어디까지 오른쪽으로 갈 수 있는지 1씩 이동시켜주면서 일일이 구했다.

정답 아이디어

• dist_left[i]를 인덱스 i번째 블록에서 왼쪽으로 갈 수 있는 거리, dist_right[i]를 인덱스 i번째 블록에서 오른쪽으로 갈 수 있는 거리라고 하자.
• dist_left 배열과 dist_right 배열은 손으로 써서 구하다 보면 O(N) 안에 구할 수 있음을 알 수 있다.
• 정답은 dist_left[i]와 dist_right[i]를 더했을 때 그 값이 최대가 되는 조합이다.
• 어떤 블록에 도착했을 때 왼쪽, 오른쪽 거리를 계속 일일이 구해주지 않고 특정 블록에서 왼쪽으로 갈 수 있는 거리, 오른쪽으로 갈 수 있는 거리를 다 구해놓고(저장해놓고) 나중에 이용하는 것으로, 이 문제는 DP로 푸는 것임을 알 수 있다.
• 따라서, 총 3N의 시간복잡도로 정답을 구할 수 있다. => 결국은 O(N)

코드

def solutions(blocks):
    N = len(blocks)
    dist_left = [0] * N
    dist_right = [0] * N
    
    #blocks[i]에서 왼쪽으로 갈 수 있는 칸의 수를 센다
    for i in range(1, N):
        dist_left[i] = dist_left[i-1] + 1 if blocks[i-1] >= blocks[i] else 0
    #blocks[i]에서 오른쪽으로 갈 수 있는 칸의 수를 센다
    for i in range(N-2, 0, -1):
        dist_right[i] = dist_right[i+1] + 1 if blocks[i+1] >= blocks[i] else 0
    
    maxDist = 0
    for i in range(N):
        if dist_left[i] + dist_right[i] >= maxDist:
            maxDist = dist_left[i] + dist_right[i]

    return maxDist + 1