[백준 1874번] 스택 알고리즘

 

< Happy New Year >

 

- 먼저 혼자짜본 코드

import sys
n = int(sys.stdin.readline())
suyeol = [int(sys.stdin.readline()) for _ in range(n)]
answer = []

if sorted(suyeol[suyeol.index(max(suyeol)):],reverse=True)==\
suyeol[suyeol.index(max(suyeol)):]:
    for i in range(1, n + 1):
        answer.append(i)
        print('+')
        while answer[-1] == suyeol[0]:
            print('-')
            answer.pop()
            suyeol.pop(0)
            if len(answer)==0:
                break
else:
    print('NO')

1. NO가 나오는 조건은 pop을 통해 최대값을 뽑아내고 낸 뒤의 값이 내림차순으로 정렬되어있을 때라는 생각 (if비교)

2. if문을 사용하지않고 while문 단독 사용시 인덱스 에러 발생

3. 새로운 answer list와 주어진 suyeol list를 각각 끝과 처음을 비교해가며 옳은경우 pop을 실행한다고 생각

-> 주어진 예제는 통과하지만 제출후 23% 이후 출력초과 에러가 발생 ( 아마 NO를 뽑아내는 기준이 부족하다고 느낌 )

 

- 새로 고친 답

import sys
n = int(sys.stdin.readline())
suyeol = [int(sys.stdin.readline()) for _ in range(n)]
stack = []
count = 1
answer = []
i = 0

while i<n:
    while count <= suyeol[i]: # count가 이미 스택에 들어가진수보다 클경우 돌아가지 않음
        stack.append(count)
        answer.append('+')
        count += 1
    if stack[-1] == suyeol[i]:
        answer.append('-')
        stack.pop()
    else: # 필요한만큼의 push를 마치고 pop을 해야하는 차례인데 pop이 불가능한 경우
        print('NO')
        break
    i += 1
else:
    for j in answer:
        print(j)

1. 기존에 생각했던 pop이 불가능한 이유를 최대값이후 내림차순 정렬이면 괜찮을 것이다 -> 해당 숫자까지의 push가 끝나고 원하는 숫자를 pop해야될때 pop하지 못할경우로 수정 

2. answer 리스트를 추가하고 while else문을 사용해 기존 NO를 출력하기 위해 처음부터 조건을 걸었던 것을 뒤로 미룸

3. while문 안의 while문을 통해 이미 스택에 들어가 있는 수를 입력받은경우 더이상 push를 진행하지 않고 pop차례로 넘김