BOJ - 스택 수열 1874번 (python)

❓ 문제 - 백준 상어 초등학교 21608번 - python 풀이법

출처 

(https://www.acmicpc.net/problem/1874)

1874번: 스택 수열

 

 

📝 문제해결법

1. 이 문제의 핵심은 일단.. 문제에 대한 이해이다.

일단 스택 수열을 만드는 방법에는 1 ~ n 수를 오름차순으로 늘어놓으면서 만든다고 했다. 이걸 이해하면 된다.

예시 1번으로 문제를 이해해보자..

예시 1번의 경우

1) 4번을 넣기 위해 1 ~ 4번을 stack에 push한 후, 4번을 스택수열에 넣기 위해 4를 pop 해준다.

2) 3번을 넣기 위해 stack에 이미 1 ~ 3번이 존재하니깐 3번을 pop 해줘서 3번을 스택 수열에 넣어준다.

3) 6번을 넣기 위해 stack에 6번은 없고 그 다음에 5번 부터 넣을 수 있으니깐 5, 6을 차례대로 push한다. 그 후 6을 스택 수열에 넣기 위해 pop 해준다

4) 8번을 넣기 위해 stack에는 5까지 존재하고 그 다음에 7번 부터 넣을 수 있으니깐 7, 8을 차례대로 push한다. 그 후 8을 스택 수열에 넣기 위해 pop 해준다.

5) 7번을 넣기 위해 stack에는 7이 존재하므로 pop해줘서 7을 스택 수열에 넣어준다.

6), 7), 8) 5, 2, 1 번도 5)과 마찬가지로  stack에 존재하니깐 스택 수열에 넣기 위해서 pop 해줘서 스택 수열을 완성할 수 있다.

 

예시 2번의 경우

1) 1번을 넣기 위해 1번을 stack에 push한 후, 1번의 스택수열을 만들기 위해 1번을 pop 해준다.

2) 2번을 넣기 위해 그 다음 2번부터 스택에 넣을 수 있으므로  2번을 stack에 push한 후, 2번의 스택수열을 만들기 위해 2번을 pop 해준다.

3) 5번을 넣기 위해 stack에 5번은 없고 그 다음에 3번 부터 넣을 수 있으니깐 3, 4, 5을 차례대로 push한다. 그 후 5을 스택 수열에 넣기 위해 pop 해준다

4) 3번을 스택 수열에 넣기 위해서 pop을 두 번 해주면 3번을 스택 수열에 넣을 수 있다.

그러나 4번의 경우 이미 스택에 들어갔다가 빠져나갔기 때문에 스택 수열을 완성할 수 없다. 

 

2. 다음과 같은 예시로 스택을 활용하여 구현할 수 있다.

• 우선 n의 값을 입력 받기
• 구성할 스택 수열의 값들을 입력받을 number 리스트와, push하고 pop하는 과정을 담을 answer 리스트, 들어간 스택 수열의 값을 담을 stack 리스트, 그리고 스택 수열을 만들기 위해서 1 ~ n의 수를 담을 stack2  을 선언
• 일단 1 ~ n의 값을 가르킬 num 을 선언, what로 만약 스택수열을 완성할 수 없을 때를 표시
• num이 완성하고 싶은 스택 수열의 값보다 작다면 스택수열을 만들 수 있게 1 ~ num 수를 stack2에 push 해주기 또한 push한 값을 answer에 '+'로 넣어주고, num값을 스택 수열의 값으로 만들어준다.
• 또한 스택 수열 값을 넣기 위해 stack2에서 해당 값을 pop해주고 answer에  '-'을 넣어주며, 스택 수열(stack2)에 넣어줌
• num이 완성하고 싶은 스택 수열의 값보다 크다면, 현재 1 ~ num의 수를 넣은 stack2의 top 값을 이용하여 top값과 스택 수열에 넣어 주고 싶은 값이 같다면 해당 값을 stack2에서 pop 해서 스택수열에 값을 넣고 anwer에 pop('-') 을 넣어줌
• num이 완성하고 싶은 스택 수열의 값보다 크다면, 현재 1 ~ num의 수를 넣은 stack2의 top 값을 이용하여 top값보다 스택 수열에 넣어 주고 싶은 값이 작다면 스택 수열에 넣어주고 싶은 값을 pop 할때까지 (diff=차이) 만큼 stack2에서 pop('-'), 스택수열에 해당 값을 넣어줌
• num이 완성하고 싶은 스택 수열의 값보다 크다면, 현재 1 ~ num의 수를 넣은 stack2의 top 값을 이용하여 top값보다 스택 수열에 넣어 주고 싶은 값이 크다면, 스택 수열에 넣고 싶은 값이 이미 stack2에 push되었다가 pop된 값이므로 스택 수열을 완성할 수 없음. 따라서 what값을 True로 변경하고 해당 for문을 break해줌
• 만약 what값이 True라면 완성할 수 없는 스택수열이므로 'No'를 출력하고, 완성할 수 있는 스택 수열이라면 스택 수열(answer)값들을 하나씩 출력해줌

 

💻 소스코드

# 스택 수열 - BOJ 1874
import sys

input = sys.stdin.readline

n = int(input())
number = []
answer = []
stack2 = []
stack = []
for _ in range(n):
    number.append(int(input()))

num = 0
what = False
for i in range(len(number)):
    if num < number[i]:
        for j in range(num+1, number[i]+1):
            stack2.append(j)
            answer.append('+')
        num = number[i]
        answer.append('-')
        stack.append(number[i])
        stack2.pop()
        continue
    else:
        top = stack2[-1]
        if top == number[i]:
            answer.append('-')
            stack.append(number[i])
            stack2.pop()
        elif top < number[i]:
            diff = top - number[i]
            for j in range(diff):
                stack2.pop()
                answer.append('-')
            stack.append(number[i])
        else:
            what = True
            break

if what:
    print('NO')
else:
    for i in answer:
        print(i)

 

 

🧐 Ellen's Thinking

단계별로 풀고 있는데 실버 문제부터 막히는 경우가 있다. 이렇게 단계적으로 풀면서 알고리즘 실력을 늘리는 방법이 좋은 것 같다. 그리고 문제 이해도가 알고리즘 풀이에 가장 중요한 것 같다. 문제를 잘 이해해보려고 노력하자 !!!