[백준][Python] 1874. 스택 수열

반응형

 

 

 

 

 

 

🙆‍♂️문제

---

 

🙋‍♂️풀이

---

문제가 말이 어렵네요. 2가지 규칙이 있습니다.

1. PUSH는 오름차순으로 ( 입력값 상관 없이)

2. POP은 입력된 값대로

 

예를 들어서 총 수(n)을 8이라고 입력 받고 4 3 6 8 7 5 2 1을 입력받았다면

1 2 3 4를 PUSH 하고 POP 해서 4를 빼고 또 POP해서 3을 빼는..

그렇게 POP해서 만든 리스트가 4 3 6 8 7 5 2 1이 되어야 합니다.

 

안되는 경우도 있는데 교착 상태에 빠지는 경우 입니다.

스택의 LIFO 특성 덕분에 a가 POP되어야 할 때 a위에 a보다 작은 b가 있다면 교착상태가 됩니다.

안되는 경우를 한 마디로 정의하면

list[i]이 list[i+1]보다 큰 경우 입니다.

 

 

🚀 입력받기

---

import sys
n = int(sys.stdin.readline())
se = [int(sys.stdin.readline()) for _ in range(n)]

n은 총 숫자의 수가 입력되고

se는 수열이 입력됩니다.

n을 통해서 1부터 n까지 입력되는 것을 알 수 있습니다.

 

🚀 문제 풀이 핵심

---

stack=[]
com=[]
cnt=1
ck=1
for i in se:
    while 1:
        if len(stack)!=0:   
            if stack[-1] == i:
                stack.pop(len(stack)-1)
                com.append("-")
                break
            else:
                if cnt > n:
                    ck=0
                    break       
                stack.append(cnt)
                com.append("+")
                cnt+=1
        else:       
            stack.append(cnt)
            com.append("+")
            cnt+=1
    if ck==0:
        print("NO")
        break

선언한 변수부터 소개하면 stack 리스트는 말 그대로 스택이라고 보시면 되고

com 리스트는 command 즉 PUSH(+), POP(-)의 결과들을 저장하고 추후에 출력하기 위해 사용합니다.

cnt 값은 스택에 PUSH하기 위해 선언했고

ck 값은 check로 만약 조건이 성립되지 않는 값이면 NO를 출력해야 하기에 이를 구분하기 위해서 사용했습니다.

 

반복문을 통해서 입력 받은 리스트 값과 같을 때 까지 PUSH하고 같다면 POP하는 형식입니다.

 

            else:
                if cnt > n:
                    ck=0
                    break       
                stack.append(cnt)
                com.append("+")
                cnt+=1

예외 상황은 POP하지 못했을 때 PUSH를 하게 되는데 이 때 PUSH할 값이 수열의 수보다 커지면 불가능한 케이스라고 판단하여 ck값을 0으로 변경합니다.

 

 

 

 

🚀 출력하기

---

    if ck==0:
        print("NO")
        break
if ck == 1:
    for i in com:
            print(i)

출력할 때 예외상항은 ck값이 0이 되면 그 즉시 반복문을 멈추고 NO를 출력하고 다시 반복문을 나오도록 합니다.

만약 ck 값이 1로 반복문이 정상종료된다면 명령어들을 저장했던 리스트의 값들을 출력합니다. 

 

728x90