[Python] 백준 1874번 스택 수열

스택 수열 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	30265	8994	6665	30.772%

문제

스택 (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

힌트

1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다.

소스코드

1차 접근 문제풀이

from sys import stdin
nums = list(range(1, int(stdin.readline())+1))
in_ = map(lambda x : int(x.rstrip()), stdin.readlines())

def numeric():
    stack, result = [], []
    for i in in_:
        while True:
            if stack and stack[-1] > i:
                return 'NO'
            if not stack or stack[-1] != i:
                stack.append(nums.pop(0))
                result.append('+')
            if stack and stack[-1] == i:
                stack.pop()
                result.append('-')
                break
    return '\n'.join(result)

print(numeric())

• 결과
  • 메모리 40276KB
  • 시간 1924ms
• 접근
  • 스택 방식으로 문제를 해결해야 하는 것은 모두 같은 생각일 것이라 생각됩니다.
  • in_의 값이 입력된 수열입니다. 수열의 값과 stack의 내용을 비교하면서 해당 스택 값이 없으면 nums에서 뽑아서 넣어주는 방식으로 진행하였습니다. 결과 시간이 상당히 오래걸리는 것에서 잘 못 풀었다는 생각을 할 수 있었습니다.
  • 1부터 N까지의 숫자 열을 만든 후 차례대로 스택에 넣고 빼는 방식으로 생각했습니다.하지만, 1부터 차례대로 증가하는 방식은 굳이 숫자열을 만들어 줄 필요 없습니다. 반복문을 돌면서 1씩 더해주면 자동으로 1씩 증가하는 숫자 열의 기능을 할 수 있습니다. 이 부분을 참고하여 아래의 풀이를 작성하였습니다.

최종 풀이

from sys import stdin
n = int(stdin.readline())
in_ = map(lambda x : int(x.rstrip()), stdin.readlines())

def numeric():
    cnt, stack, result = 1, [], []
    for i in in_:
        while cnt <= i:
            stack.append(cnt)
            result.append('+')
            cnt+=1
        if stack.pop() != i:
            return 'NO'
        else:
            result.append('-')
    return '\n'.join(result)

print(numeric())

• 결과
  • 메모리 37664KB
  • 시간 140ns
• 풀이
  • while문을 돌면서 해당 값 까지의 숫자들이 모두 들어왔는지 확인한 후 부족하면 pop기능을 계속 수행합니다.
  • pop한 값이 in_의 입력된 수열 값과 다르면 NO를 출력합니다.
  • pop 명령을 실행하면 바로 값이 빠져나가서 더 이상 리스트에는 해당 값이 없습니다. 따라서 if조건문에서 pop을 이미 수행하였으므로 else에서는 값을 비교하지 않고 pop을 수행한 것을 표현하는 -만 result리스트에 넣어주었습니다.

• 유사한 문제

2020/02/16 - [파이썬] - [Python] 백준 4949번 균형잡힌 세상

[Python] 백준 4949번 균형잡힌 세상

2020/02/15 - [파이썬] - [Python] 백준 10773번 제로

[Python] 백준 10773번 제로

2020/02/15 - [파이썬] - [Python] 백준 10828번 스택

[Python] 백준 10828번 스택

 

• 문제 출처

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

1874번: 스택 수열