[백준] 1874번 스택 수열 - Python(파이썬)

https://www.acmicpc.net/problem/1874

1874번: 스택 수열

 

문제

 

 

21.02.12 접근법

 

1부터 num까지 계속 반복

1부터 push하고 + 저장

이후, stack에 마지막 저장된 것과 num 동일할 시 pop과 - 저장

하지만, 시간 초과로 실패

import sys

n=int(input())
loca=0
check=[False for i in range(n+1)]
answer=[]
stack=[]    

for j in range(n):
    num=int(sys.stdin.readline().strip())
    for i in range(1,num+1):
        
        if check[i]==False:
            stack.append(i)
            check[i]=True
            answer.append('+')

        try:   
            if stack[-1]==num:
                stack.pop()
                answer.append('-')
                loca+=1
                break
        except:
            pass
if len(stack)!=0:
    print("NO")
else:
    for i in range(len(answer)):
        print(answer[i])

 

몇 시간 시도를 했지만, 되풀이되는 실패

결국, 검색해보았고 하나의 깨달음을 얻게 되었다.

1. 오름차순 push이므로 순차적으로 한번만 push하면 됨. (1부터 계속 돌릴 필요 없음.)
2. 스택에 마지막으로 저장되어있는 값과 num이 일치하면 pop

딱, 이 두 개로 코드를 정리하니 시간 초과도 안 뜨고 통과하였다.

 

21.02.12 코드

import sys
n=int(input())
ck=1
answer=[]
stack=[]   

for j in range(n):
    num=int(sys.stdin.readline().strip())

    for i in range(ck,num+1):
        stack.append(i)
        answer.append('+')
        ck+=1

    if  stack[-1]==num:
        stack.pop()
        answer.append('-')

if len(stack)!=0:
    print("NO")

else:
    for i in range(len(answer)):
        print(answer[i])

 

21.07.19 접근법

 

  ▶주요 변수들 

• start : push할 시작점
• stk : 수열을 만들기 위한 스택
• loca : 수열의 진행 단계 위치로 현재 다뤄야 할 숫자

 

3가지로 구분하여 진행

1. stk이 비어있거나 stk의 top이 현재 다뤄야 할 숫자 loca보다 작을 때
2. stk의 top이 loca와 같을 때
3. stk의 top이 loca보다 클 때 loca보다 크면 수열을 만들 수 없으므로 종료

 

 

21.07.19 코드

import sys

def plus(num):
    stk.append(num)
    answer.append('+')

def minus():
    stk.pop()
    answer.append('-')

 
stk=[]
answer=[]
start=1

  
n=int(input())

for _ in range(n):
    loca=int(sys.stdin.readline())

    if not stk or stk[-1]<loca:
        #push and pop
        for i in range(start,loca+1):
            plus(i)
        minus()
        start=loca+1
        
    elif stk[-1]==loca:
        #pop
        minus()

    elif stk[-1]>loca:
        #NO!
        print('NO')
        sys.exit()

for _ in answer:
    print(_)