[자료구조] [python] Queries with Fixed Length (min-max)

Hackerrank의 Data structures 관한 문제 중에서 Hard(success rate 60%)에 속하는 문제이다. 원 문제 링크는 다음을 따라가보자. 

www.hackerrank.com/domains/data-structures?filters%5Bstatus%5D%5B%5D=unsolved&filters%5Bstatus%5D%5B%5D=solved&filters%5Bsubdomains%5D%5B%5D=queues&badge_type=problem-solving

Solve Programming Questions | HackerRank

 

• 쉽게 풀릴 것 같으면서도, 시간 내에 test case가 돌아가지 않아 애먹었던 문제다. window 크기만큼 리스트를 슬라이싱해서 max()함수를 쓰면, 시간 내에 테스트 케이스가 돌아가지 않는다. query의 크기만큼 window를 밀어가면서, 새로 들어오는 끝원소와, 앞쪽의 원소의 값을 이전 시점(t-1)의 최대값과 비교하면서 값을 새로 업데이트 하는 방식으로 풀었다. 앞의 빠지는 원소가 이전 시점의 최대값이라면, 새롭게 윈도우 내에서의 max()값을 구하는데, 이렇게 구해도 시간 내에 효율적으로 돌아가는 코드인 점이 신기하였다. 

 

def solve(arr, queries):
    result = []
    
    for q in queries: 
        max_value = max(arr[:q])
        min_value = max_value
        
        for i in range(q, len(arr)):
            if arr[i-q] == max_value:
                max_value = max(arr[i-q+1:i+1])
            elif arr[i] > max_value:
                max_value = arr[i]
            if min_value > max_value:
                min_value = max_value
        
        result.append(min_value)

    return result