[BEAKJOON] 백준 1874번 : 스택 수열

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

1874번: 스택 수열

 

문제 설명

처음에 이 문제의 의미를 제대로 이해하지 못했다. 뭔 뜻이지? 하고 문제가 무슨 뜻인지 이해하는지 1분 넘게 걸린 것 같다.

 

만약에 첫 예제 입력 1에 대한 설명을 해보겠다.

같이 N = 8로 주어졌을때, 1~8이라는 숫자가 존재한다.

입력 값이 4, 3, 6, 8, ... 로 진행되는데,

1부터 8까지 순회를 한다. 첫 입력 값이 4이기 때문에 4까지 push 가 4번 진행된다. 그러므로 "+" 출력이 4번 되는 것이다.

push가 4번 되고,  stack에는 순서대로 1, 2, 3, 4가 들어있을 것이다. +(push 1) +(push 2) +(push 3) +(push 4)

그러면 첫 입력 값은 4이기 때문에 pop을 한번 진행한다. -(pop 4)

stack에는 마지막 4가 빠진 1, 2, 3가 들어가 있다. 그 다음 두번째 입력 값은 3이기 때문에 pop을 한번 진행한다. - (pop 3)

stack에는 3이 빠진 1, 2가 존재한다. 그 다음 세번째 값은 6이기 때문에 push를 6이 나올 때까지 진행한다. 그러면 push는 두번이 진행된다. +(push 5) + (push 6)

stack에는 1, 2, 5, 6이 존재한다. 그리고 6을 빼주기 위해서 pop을 한번 해준다. - (pop 6)

stack에는 1, 2, 5가 존재할 것이다. 다음 입력 값은 8이기 때문에, push를 두번 진행해준다. + (push 7), + (push 8)

stack에는 1, 2, 5, 7, 8이 존재한다. 이어지는 입력 값인 8과 7을 빼기 위해 pop을 한번 해준다. - (pop 8), - (pop 7)

stack에는 1, 2, 5가 존재한다. 차례대로 값을 다 빼주면 된다. - (pop 5), - (pop 2), - (pop 1)

 

 

 

 

프로세스 설명

초기화

1. stack_list와 print_list를 1 하나를 넣어준다. 왜냐하면 처음 값은 무조건 1이며, n은 1보다 큰 값이기 때문이다.

2. last_num의 값도 1로 초기화 해준다.

3. 처음 N의 값을 입력 받아준다.

 

프로세스

1. N번 반복문 진행으로 매번 num의 값을 받아준다.

2. 만약에 last_num이 받아준 num의 값보다 크지 않을 경우 계속 while 반복문을 진행해준다.

- 처음에는 같지 않을 경우(=!)를 시도했었는데, 그렇게 되면 반복된 값이 진행되기 때문에 작을경우(<)로 진행해준다.

3. last_num의 값에 1을 더해주고, stack_list 를 1을 더해준 last_num을 넣어준다.

4. print_list 에도 1을 더해준다. 1을 더해준다는 것의 의미가 +를 출력해주는 것이다.

- 처음에 그냥 +로 출력해줬는데, NO의 경우일 때 출력을 하면 안됐어서, 리스트로 넣어주는 방법을 사용했다.

5. 만약에 마지막 값이 num과 같을 경우에는 print_list에 0을 넣어준다. 즉 "-"를 출력하게 해준다.

6. last_num < statck_list[-1]일 경우에만 last_num의 값을 넣어준다.

- 처음에는 if문을 예외처리를 안해줬는데, 그러니까 다시 작은 값으로 중복되어 출력되는 현상이 있었기에 예외처리 해주었다.

7. stack_list의 pop을 해준다.

8. 마지막으로 1일 경우 출력 "+"해주고, 0일 경우 "-"를 출력해준다.

9. stack_list의 길이가 0이 아닐 경우에는 잘 안됐다는 거니 "NO"를 출력해준다.

 

---

최종 코드

import sys
input = sys.stdin.readline

stack_list = [1]
last_num = stack_list[-1]
print_list = [1]

N = int(input())

for i in range(0, N):
    num = int(input())
    while(last_num < num):
        last_num+= 1
        stack_list.append(last_num)
        print_list.append(1)
    if(stack_list[-1] == num):
        print_list.append(0)
        if(last_num < stack_list[-1]):
            last_num = stack_list[-1]
        stack_list.pop()

if(len(stack_list) == 0):
    for i in print_list:
        print("+" if i else "-")
else:
    print("NO")