오늘의 알고리즘(4월 6일)

 1. 백준, 스택수열, 1874번 

 

www.acmicpc.net/problem/1874

1874번: 스택 수열

 

---

2. 생각해보자 

- 먼저, 문제에서 주어진 정보를 정리해보자.

 

1) 스택을 구현한다. (LIFO 특성) 

 

2) push 와 pop 메소드를 사용한다. 

 

3) 첫번째 입력값 n이 입력된 다음부터 입력되는 정수의 개수다.

ex) 8이 첫번째 입력값이라면 이를 제외하고 앞으로 8개 정수가 더 입력된다. 

 

4) 주어지는 숫자의 범위는 1부터 n 까지다. 

 

5) push는 +로, pop은 -로 표시한다. 

 

6) push 순서는 반드시 오름차순을 지킨다. 

 

- 예제 입력과 출력을 살펴보면 문제를 더 이해하기 쉽다. 

- 예제 입력에서 4를 어떻게 pop할지 생각해보자. 4가 될 때까지 1부터 4까지 push한 후 pop을 하면 되는 것이다. 

- 이것을 코드로 구현해보자. 

 

---

3. 풀이 및 코드분석

 

n = int(input())

count = 1 #1부터 n까지 증가할 숫자
stack = [] #데이터가 쌓일 스택
result = [] #push와 pop을 기록할 배열

for i in range(1, n + 1): #첫번째 입력값 n개 만큼 반복
	data = int(input())
    
    while count <= data: #입력받은 데이터에 도달할 때까지 push
    	stack.append(count)
        count += 1
        result.append('+')
        
    if stack[-1] == data: #스택의 최상위 원소가 데이터와 같을 때 출력
    	stack.pop()
        result.append('-')
        
    else: #오름차순의 push 또는 최상위 원소가 데이터와 달라서 pop을 못하는 경우 
    	print('NO')
        exit(0)
        
print('\n'.join(result)) # for문이 완료 후 출력