joseph

1874번: 스택 수열 (acmicpc.net)

문제이해

1부터 순서대로 쌓여가는 스택에서 내가 원하는 수열에 필요한 값들이 나타나면 빼온다. 이 과정을 기록한다.

접근하기

1. 실제 스택을 구현해서 사용할 필요 없다. 리스트에도 pop()기능이 있다.

2. 출력할 +, - 를 담을 리스트를 따로 만들어서 리스트(res)를 출력하자.

3. 스택에는 1,2 ... , 입력값(n)까지 순서대로 쌓아 나간다.

     쌓는게 가능한 상황이면 res에 +를 append 하고 불가능한 상황이면 가능한 상황일때까지 -를 append 하자.

4. 입력한 요소는 바로 수열로 나와야 한다. 입력할때마다 if문에 걸려서 pop() 해주면 될 거 같다.

     즉 스택에는 내가 원하는 수열에 해당하는 값들이 지워지게 된다.

5. n만큼 반복해야하고, 그 안에서 + - 썼다 지웠다 해야할 거 같다. 

6. count 변수를 따로 쓰는 이유 : 반복문이 돌아도 초기화 되면 안된다.

코드

#최대 스택 크기 10000에 대한 조건은 안 줬는데 정답 처리 됐다.
stk=[]
res=[]
count=1 
flag=True

n=int(input())
for i in range (0,n):
    ele=int(input())     # 입력값 = 수열에 필요한 값
    while(count<=ele):
        stk.append(count)   # 스택에 순서대로 쌓기. 입력값 만큼 쌓는다
        res.append('+')       # push(쌓기)될 때마다 + 를 배열에 추가
        count+=1
    
    if(stk[-1]==ele):   # 현재 스택의 마지막 값과 방금 입력한 값이 같을 떄.

                               즉 입력한 값은 수열에 써야되니까 스택에서 뺀다.
        stk.pop()        # 리스트에서도 pop을 지원한다. 스택의 pop과 동일하다.
        res.append('-') 
    
    else:
        flag=False      # 위 규칙대로 스택에서 값을 가져오는게 불가능하면 스택으로 수열을 못 만든다는 말이다.

if (flag==False):
    print('NO')
else:
    for i in res:
        print(i)