[Baekjoon] 1874_스택 수열

Silver III

문제(출처: https://www.acmicpc.net/problem/1874)

---

<스택 수열>

문제 

 

스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다.
스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는
(LIFO, Last in First out) 특성을 가지고 있다.
1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push 하는
순서는 반드시 오름차순을 지키도록 한다고 하자.
임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로
push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라.

 

입력

 

첫 줄에 n (1 ≤ n ≤ 100,000)이 주어진다. 둘째 줄부터 n개의 줄에는 수열을 이루는 1 이상 n이하의
정수가 하나씩 순서대로 주어진다. 물론 같은 정수가 두 번 나오는 일은 없다.

 

출력 

 

입력된 수열을 만들기 위해 필요한 연산을 한 줄에 한 개씩 출력한다.
push연산은 +로, pop 연산은 -로 표현하도록 한다. 불가능한 경우 NO를 출력한다.

 

 

문제 풀이

   - my solution

import sys

if __name__=='__main__':
    n=int(sys.stdin.readline().strip())

    arr=[]
    for i in range(n): #수열 입력
        arr.append(int(sys.stdin.readline().strip()))

    idx=0
    idx_stack=1
    temp=[] #오름차순 push
    answer=[] # +,-
    result=[] # 만들어진 수열
    while True:
        if idx>=n or idx_stack>n+1: #종료 조건
            break
        if len(temp)!=0 and temp[-1]==arr[idx]: #temp에 이미 있는 값 pop
            result.append(temp.pop())
            answer.append("-")
            idx+=1
        elif arr[idx]!=idx_stack: # push
            temp.append(idx_stack)
            idx_stack+=1
            answer.append("+")
        elif arr[idx]==idx_stack: # 넣으려는 값이 필요한 값이면
            result.append(idx_stack) # push 전에 바로 result에 추가
            answer.append("+") # puxh
            answer.append("-") # pop
            idx_stack+=1
            idx+=1

    if arr==result: # 만들어진 수열이 입력 수열과 같으면
        for i in answer:
            print(i)
    else: # 불가능한 경우
        print("NO")

 

예전부터 문제만 보고 이해를 못해서 포기했던 문제이다.

차근차근 살펴보니 생각보다 문제를 이해하기 쉬웠다.

 

1) n입력, 만들 수열 입력_arr

2) while문을 사용하여 수열 만들기

  2-1) 종료 조건) arr의 index를 넘거나 n+1보다 큰 경우

  2-2) temp에 이미 있는 값이면 pop

  2-3) idx_stack이 필요한 값이 아니면
  2-4) idx_stack이 수열에 필요한 값이면 push

3) 만들어진 수열이 입력 수열과 같으면 출력, 같지 않으면 'NO' 출력

---

생각🤔

 

몇 번이나 지나친 문제 치고는 생각보다 빨리 해결할 수 있었다.

문제 이해를 못했던 것이 컸던 것 같다. 문제를 이해하고 나서는 금방 코드를 구현할 수 있었다.

파이썬에서는 list를 활용하여 이 문제를 해결할 수 있었다.

 

내가 생각하기에 이 문제의 포인트는

1) 문제 이해!!! 가 가장 크고

2) 파이썬_ list의 활용, 조건문 사용

이었던 것 같다.

 

---