스택 - 백준 1874

스택이란 Last In First Out의 구조를 갖는 자료구조의 일종이다.

이를 구현하는 문제들을 전부 풀어보았는데 가장 고난이도 문제를 가져왔다

 

스택은 전에 공부한 적이 있어서 꽤 수월하게 풀어냈다.

 

바로 문제를 보자

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

1874번: 스택 수열

 

n = int(input()) #전체 숫자 갯수
stack = []
answer = []
flag = 0 #가능여부를 따지는 flag
cur = 1 #오름차순으로 숫자를 넣으므로 거기에 사용할 currentNumber
for i in range(n):
    num=int(input())
    while cur <= num : #num을 제일 먼저 출력해야하므로 stack의 마지막에 올때까지 담는다
        stack.append(cur)
        answer.append('+')
        cur += 1
    if stack[-1] == num : #stack의 맨 마지막 숫자와 num이 같다면 출력한다.
        stack.pop()
        answer.append('-')
    else :
    #여기서 출력해야하는 숫자가 cur보다 작고 stack의 마지막에 있지 않으면 Error이다.
    #왜냐하면 오름차순으로 숫자를 담았기 때문에 cur보다 작은 숫자들은
    #이미 stack안에 있기 때문이다.
        print('NO')
        flag = 1
        break
if flag == 0 :
    for i in answer :
        print(i)

이렇게 문제를 풀어봤다.

정보처리기사 공부하면서 자료구조에 대해서도 나오는데 알고리즘풀이를 공부하다보니

기사준비가 꽤나 수월하다.

 

알고리즘을 모두 정복하는 그날까지 화이팅!