[알고리즘/자료구조] 1874번 : 스택 수열 - python

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

1874번: 스택 수열

 

---

• 문제
• 소요시간:62분 20초

---

• 설계하기(접근방법) 

1. n 을 입력받는다

스택 리스트 = []

pushpop 리스트

2. 알고리즘 설계

1) 먼저 스택을 생성한다.

2-1) 기준 숫자보다(초기값 : 0) 큰 숫자가 들어오면 그숫자까지 stack에  push한다stack =  [1,2,3,4]

2-2) 기준 숫자보다 작은 숫자가 들어오면 그 숫자가 stack[-1](리스트의 마지막 원소)인지 검사한다

2-2-1) 맞으면 pop()

2-2-2) 틀리면 print('No') 후 break한다.

3) append할때마다 ('+') , pop 할때마다 ('-')를 pushpop 리스트에 append 한다

3. pushpop 리스트를 출력한다.

---

• 코드(출력)

import sys

input = sys.stdin.readline

n = int(input())

pushpop = []
stack = []
temp = 0


for i in range(n):  # 1. 4 3 2
    x = int(input())
    if x > temp:  # 4 > 0
        for i in range(temp + 1, x+1):  # stack = [1,2,3,4]
            stack.append(i)
            pushpop.append('+')
        stack.pop()  # 4 pop
        pushpop.append('-')
        temp = x
    else:  # 3 < 4
        if stack[-1] == x:  # stack[-1] == 3
            stack.pop()  # stack.pop() = [1,2]
            pushpop.append('-')
        else:
            print('NO')
            break

if len(pushpop) == 2*n:
    for i in pushpop:
        print(i, end=' ')

---

• 얻어갈 부분

1. 문제를 읽을 때 독해를 잘해야겠다. 지문이 어려운 경우 천천히 읽고, 예시를 써보면서 문제를 풀자