알고리즘 자료구조/Stack

1874번 스택수열 파이썬

Zeta050525 2022. 1. 8. 16:25
728x90

문제

스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다.

1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push 하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라.

입력

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

출력

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

 

내가 접근한 방법

없다.

문제 자체를 이해하는데 좀 걸렸습니다.

풀이를 봤는데도 이해가안갔어요.

멘붕이 와 서 그냥 풀이들만 주구장창봤습니다.

계속 계속 봤어요 그냥

보고 보고 보다가 갑자기 띠용 하면서 약간 정리가 됐는데

그때부터 약간 차근차근 이해가 갔습니다.

별로 안궁금하실테니까 여기까지하겠습니다.

 

풀이

8
4
3
6
8
7
5
2
1

입력이 이런 식으로 들어왔다고 치자

stack = []

result = []

1부터 4까지 스택에 넣는다

1234 

4를 만났을 때 pop 하면서 result에 push

result = [4]

stack = [1~3]

stack의 top이 3이니까

3도 pop하면서 result에 push

stack에 5부터 시작해서

6까지 push

이런 식으로 하면 4 3 6 8 7 5 2 1을 만들 수 있습니다.

 

사실 글로만 보면 이해가 안가 실수도 있습니다. (제가 멍청해서 저만 그런 걸 수도 있음)

이 문제는 그림을 봐야지 이해가 가더라고요 제가 글을 잘 못쓰는 것도 있고

 

이어서 NO가 나오는 경우도 해보겠습니다

 

5
1
2
5
3
4

 

1 push

stack top이 1이랑 같으니까 pop

2 push

마찬가지로 pop

5를 만났으니까

3~5까지 push

5 때 pop

이때 stack [3,4]

다음 입력은 3

6을 push 해야 하는데 입력으로 3이 들어왔죠

이러면 NO입니다.

왜냐하면

이때, 스택에 push 하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 

라고 되어있기 때문입니다.

정답 (python)

n = int(input())

answer = list()
stack = list()
state = True
i = 0
for _ in range(n):
    num = int(input())
    while i < num:
        i += 1
        stack.append(i)
        answer.append("+")
    if stack[-1] == num:
        stack.pop()
        answer.append("-")
    else:
        state = False


if state:
    for i in answer:
        print(i)
else:
    print("NO")

주의하실 점은

i를 for문안에 선언해버리면 안 됩니다

728x90