백준-1874 스택수열

Yeom Jae Seon·2021년 2월 9일
0

알고리즘

목록 보기
12/19
post-thumbnail

문제 ❗

스택문제이다.
입력된 수열이 되기 위해선 오름차순으로 push하는 방식의 stack을 push와 pop을 얼마나 해야할지에 대한 문제이다.
여기서 힌트는 push를 오름차순으로 한다는 것이다.
처음에 문제가 이해가 잘가지않았는데
예시를 보며 노트에 직접써가며 해보니 쉽게 문제는 이해가 됐다.

푼 방법 😁

문제를 고민하다 착안한 내용은 입력된 수열중 값이 작아지는건 연속으로 pop이 이루어진 것이고 수열의 다음수가 값이 커지는건 그만큼 push가 되었다는 것이다.
여기서 부터 문제를 풀기 시작했다.

stackArr를 빈배열로 먼저 만든다음
입력된 수열이 있는 리스트를 순회하며 풀었다.
그전에 j라는 하나의 변수를 만들었는데 이 변수는
1부터 차근차근 입력할 변수이다.(오름차순으로 push되므로)

입력된 수열이 저장된 resultArr 리스트를 순회하면서 j(j는 1부터임.)가 resultArr[i]가 j보다 크거나 같다면 stackArr에 push가 이루어져야한다. 그래서 j가 resultArr[i]보다 커질때까지 (정확힌 1이더 크겠다.) stackArr에 j를 넣고 stackArr의 마지막 원소와 resultArr[i]가 같다면 pop을 하고 다르다면 수열이 만들어질수 없으므로 break해서 리스트 순회를 끝냈다.

이문제는 근본적으로 리스트로 appendpop을 통해서 푸는 문제였고 오름차순으로 push가 된다는 힌트를 통해 어렵지 않게 풀수있었다.

다만 문제를 맞닥뜨렸을때 문제 자체가 이해가잘안되서 조금 힘들었다.

코드 😀

# 결과 수열이 1씩 작으면 바로 pop이루어진것
# 결과 수열이 갑자기 커지면 push가 이루어지고 그뒤에 
# pop이이루어진것

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

resultArr = []

for i in range(n):
  resultArr.append(int(sys.stdin.readline().rstrip()))

# print(resultArr)

stackArr = []

printArr = []

j = 1 # stack에 입력되는 수
for i in range(len(resultArr)):
  while j <= resultArr[i]:
    stackArr.append(j)
    printArr.append('+')
    # print("+")
    j += 1
    # print(stackArr)
  if resultArr[i] == stackArr[len(stackArr) - 1]:
    stackArr.pop()
    printArr.append('-')
    # print("-")
    # print(stackArr)
  else:
    printArr = ['NO']
    break;

for i in range(len(printArr)):
  print(printArr[i])

0개의 댓글