[BOJ] 1874. 스택수열(python)

📌문제

💪아이디어

1. 주어진 수열 만들 수 있는지 검사
   max 값은 해당 인덱스의 수열값을 갱신해 가면서 검사해 줬다. max의 최댓값은 n이다.
   n에 도달하면 그다음부터는 작은 수가 나올테니까 max값을 stack의 맨 위의 값으로 갱신하가면서 True,False검사하는 범위를 줄여줬다.
   • max값과 비교
     
     • arr[i]>max: arr[i]-max만큼 +출력하고 / -출력/ False / max=arr[i]
       
     • arr[i]<max: max보다 작은 수들 중 제일 가까운 True 찾기 (j) –> 이 j값이 stack[-1]
       stack[-1]값과 arr[i]이 다르면 stack의 LIFO으로 인해 못만드는 배열
       같으면 False로 바꾸고 -출력
       
     • if max == n: max = j : 검사 범위 줄이기
       

🥂코드

def is_possible(arr,n):
    answer = []
    nums = [True]*(n+1)
    max_val = 0
    chk=0
    for num in arr:
        if max_val < num:
            for _ in range(max_val,num):
                answer.append('+')
            max_val = num
            nums[num] = False
            answer.append('-')
        else:
            for i in range(max_val-1,-1,-1):
                if nums[i]:
                    if i==num: 
                        answer.append('-')
                        nums[i]=False
                        if max_val==n: chk=1
                        if chk: max_val=i
                        break
                    else: return False
    return answer

arr = []
n = int(input())

for _ in range(n):
    arr.append(int(input()))

answer = is_possible(arr,n)

if answer: 
    for a in answer: print(a)
else: print('NO')