GPT로 만든 문제- 수열에서 자신보다 작지 않은 수들의 구간 찾기

GPT가 만든 Monotonic Stack 문제 - 수열 A가 주어졌을 때, 각 원소 A[i]를 기준으로 자기보다 작지 않은 수들이 연속된 가장 넓은 구간을 찾으시오.구간은 왼쪽과 오른쪽으로 확장할 수 있으며, A[i]보다 작은 수가 나오면 거기서 멈춰야 합니다.

 

 

문제 

 

수열 A가 주어졌을 때, 각 원소 A [ i ]를 기준으로 자기보다 작지 않은 수들이 연속된 가장 넓은 구간을 찾으세요.

구간은 왼쪽과 오른쪽으로 확장할 수 있으며, A [ i ]보다 작은 수가 나오면 거기서 멈춰야 합니다.

 

 

입력 & 출력

 

 

입력 - [2, 4, 4, 1, 4, 4, 4, 2]

출력 - [3, 2, 2, 8, 3, 3, 3, 4]

 

 

 

관련 포스트

 

[Python] 백준 - 6549 히스토그램에서 가장 큰 직사각형

[Python] 백준 - 3015 오아시스 재결합

 

- 코드

 

1. Monotonic Stack

import sys
from collections import deque
input = sys.stdin.readline

an = [2, 4, 4, 1, 4, 4, 4, 2]
'''
입력 [2, 4, 4, 1, 4, 4, 4, 2]
출력 [3, 2, 2, 8, 3, 3, 3, 4]
'''

def Mono_left(an):
    stack = []
    ans = [0 for _ in range(len(an))]
    for i in range(len(an)):
        while stack and an[stack[-1]] >= an[i]:
            stack.pop()
        if stack:
            lth = i - stack[-1] # 자기 자신 포함
        else:
            lth = i + 1 # 자기 자신 포함
        ans[i] = lth
        stack.append(i)
    print(ans)
    return ans

def Mono_right(an):
    stack = []
    ans = [0 for _ in range(len(an))]
    for i in range(len(an)-1, -1, -1):
        while stack and an[stack[-1]] >= an[i]:
            stack.pop()
        if stack:
            lth = stack[-1] - i
        else:
            lth = len(an) - i
        ans[i] = lth
        stack.append(i)
    print(ans)
    return ans

left = Mono_left(an)
right = Mono_right(an)
ans = [0 for _ in range(len(an))]
for i in range(len(an)):
    ans[i] = left[i] + right[i] - 1
print(ans)