[boj] 1874. 스택수열

Category	ps/자료구조
Tag	자료구조
Tags	stack
난이도	실버 3
발행 여부
사이트	boj
실수 유형
이해	완벽히 이해
최종 편집 일시	@2021년 11월 24일 오후 10:21
푼 날짜	@2021년 11월 23일 오후 11:14

문제 해설 및 주의사항

원문

문제

입력

출력

예제 입력 1

예제 출력 1

예제 입력 2

예제 출력 2

주의사항

풀이

내 풀이 코드

풀이 코드

퇴고

문제 해설 및 주의사항

원문

문제

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

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

입력

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

출력

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

예제 입력 1

8
4
3
6
8
7
5
2
1

예제 출력 1

+
+
+
+
-
-
+
+
-
+
+
-
-
-
-
-

예제 입력 2

5
1
2
5
3
4

예제 출력 2

NO

주의사항

---

풀이

8 4 3 6 8 7 5 2 1

1 2 3 4 5 6 7 8 이 정렬된 값들이다.

4 3 6 8 7 5 2 1 을 만들어야 한다.

모든 연산을 수행했을 때, stack 이 비어있지 않다면, 불가능하다는 뜻이다.

내 풀이 코드

import sys
from collections import deque

n = int(sys.stdin.readline())

seq = [int(sys.stdin.readline()) for _ in range(n)]
stack = deque()
sorted_seq = sorted(seq)
ans = []
seq_index, sorted_seq_index = 0, 0

while seq_index < n or sorted_seq_index < n :
  if stack and seq[seq_index] == stack[-1] :
    seq_index += 1
    stack.pop()
    ans.append('-')
  elif sorted_seq_index >= n :
    break
  else:
    stack.append(sorted_seq[sorted_seq_index])
    sorted_seq_index += 1
    ans.append('+')

# stack 이 남아있다면
if stack :
  print("NO")
else:
  for ch in ans:
    print(ch)

• 발상만으로 접근한 것이라서 매우 더러운 코드이다.

• seq 라는 입력 값의 list 와 sorted_seq 라는 정렬된 리스트가 있다.

• seq_index 와 sorted_seq_index 가 각 리스트를 순회한다.

• stack 의 peek 와 seq 의 현재 값이 같다면 - 연산을. 아니라면 + 연산을 해준다.
  • 예외 처리 해주는 부분이 elif 부분인데, 만약 sorted_seq_index 가 먼저 끝에 도달하면 답이 없는 것이므로 while 문을 탈출한다.

풀이 코드

n = int(input())
count = 0
stack = []
result = []
no_message=True

for i in range(0,n):
    x = int(input())

    while count < x:
      count += 1
      stack.append(count)
      result.append("+")

    if stack[-1]==x:
        stack.pop()
        result.append("-")
    else:
        no_message = False
        exit(0) #a clean exit without any errors / problems

if no_message==False:
    print("NO")
else:
    print("\n".join(result))

• 1부터 n 까지의 수가 input 인 것에 착안하였다.

• 입력 받는 순간에 각 수를 처리한다.
  • 일부러, 정렬된 리스트로 처리할 필요 없었다.

• 현재 index 보다 x 가 크면 + 연산을 해주고, 같으면 - 연산을 해주었다.

---

퇴고

• 문제를 잘 읽지 않았다.
  • input 이 n 과 1 ~ n 까지의 수로 이루어진 것이라는 것을 몰랐다.