[Do-it! 코딩 테스트-기초편] 011. 스택으로 수열 만들기

문제

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

1874번: 스택 수열

---

접근

데이터 크기: 100,000

시간 제한: 2초

 

스택을 사용하는 문제이다.

어떤 수열이 입력되면, 스택 동작 push, pop 만으로 만들어질 수 있는 수열인지 알아보는 문제이다.

스택에 push되는 값은 오름차순이어야한다.

---

코드

N = int(input())

from_list = list(range(N, 0, -1))
temp_list = [0]
to_list = []
result = []
no = False
# 1
for i in range(N):
    to_list.append(int(input()))
# 2
at = 0

# 3
while at < N:
	# 4
    if temp_list[-1] != to_list[at]:
        if len(from_list) == 0:
            no = True
            print('NO')
            break
        temp_list.append(from_list.pop())
        result.append('+')
	# 5
    else:
        result.append('-')
        at += 1
        temp_list.pop()
        
# 5
if not no:
    for i in result:
        print(i)

---

설명

증가하는 숫자를 바로 push해도 되지만 쉽게 연상되도록 from_list를 만들어주었다.

from_list는 N부터 1까지의 내림차순 리스트이고, pop을 하면 가장 작은 수 부터 얻을 수 있다.

temp_list는 from_list에서 뽑은 숫자를 그대로 push하여 가장 마지막 인덱스(가장 마지막에 push된)와 수열을 비교하기 위한 리스트이다.

 

# 1

to_list는 수열을 저장할 리스트이다. 

 

# 2

to_list 수열의 값을 하나씩 접근하는 인덱스 변수이다.

 

# 3

to_list 수열의 모든 인덱스를 비교했다면 while문 종료

 

# 4

temp_list 마지막 인덱스와 to_list 수열의 값이 다르다면 계속 from_list를 pop하기 위한 부분이다.

from_list pop -> temp_list push -> temp_list[-1]과 수열 비교

 

만약 from_list에서 더이상 pop을 할 수 없고 수열과의 비교에도 통과하지 못했다면 print('NO')

 

# 5

push는 '+'

pop은 '-'

 

# 6

결과는 result에 리스트로 저장하고 만약 스택이 수열을 만들 수 없다고 판별이 나면 결과 list를 출력하지 않는 형식.