[Algorithm] BOJ 1874번_스택수열

Backjoon Online Judge를 통해 스터디 중인 알고리즘 스터디 모임 과제입니다.
*알고리즘 스터디 모임 : 넥스터즈 8, 9기 개발자 5명으로 구성

사이트

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

문제

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

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

입력

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

출력

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

풀이

# Baekjoon Online Judge Q)1874
# Language : python3
# Version : 3.5.2
# Date : 2017. 03. 07
# Junyoung Jung(@sauber92)
# Reference : http://qkqhxla1.tistory.com/652

loop = int(input())
stack = []
result = ''    # 결과값이 들어갈 배열
index = 1      # 스택의 크기를 알아내는 변수
flag = True    # 예외처리를 할 변수

for i in range(loop):
    value = int(input())

	# 예외처리
	# 문제의 조건에서 첫번째 입력(loop)만큼의 수열이 생성되므로,
	# 두번째부터 입력되는 값(value)은 이를 넘을 수 없다.
	# 또한 스택의 마지막 요소는 입력값(value)보다 클 수 없다.
    if value > loop or (len(stack) > 0 and stack[-1] > value):
        flag = False
        break

    while True:
        if index > value:
            break

	# 스택에 1부터 값을 하나씩 push 한다.
        stack.append(index)
        result += '+\n'
        index += 1

    # 스택에서 pop 한다.
    stack.pop()
    result += '-\n'

# 결과값의 출력과 예외처리 하는 부분
if flag:
    print(result[:-1])
else:
    print('NO')

느낀점

어렵다…이 문제는 머리로는 규칙을 찾았지만 코드로 구현을 못했다. 결국 한 블로거님의 포스팅을 보고 답을 맞출 수 있었다. 앞으로 이 분의 블로그를 자주 방문할 거 같다…

이 풀이에선 예외처리하는 부분을 bool변수를 사용하여 따로 뺐다. 좋은 방법이다.

그리고 특이하게 이 풀이를 PyPy3로 제출하였을 때와 Python3로 제출하였을 때 결과가 다르다. PyPy3가 Python3보다 시간이 적게 든다고 하던데, 이것도 100% 확신할 수 있는 건 아닌가보다.

< 신기하다 >

이와 관련해서 BOJ 슬랙에 질문을 해보았다.

< wookje님, baekjoon님 감사합니다!!!!! >

최백준님께서 알려주신 내용으론, PyPy3는 경우 수학계산이 많을 때 Python3보다 빠르다고 한다. 따라서 단순하게 스택에 push, pop하게 짜여진 내 코드는 Python3에서 통과할 수 있었나보다