일단 처음에는 내가 목표하는 수열을 input으로 다 받은 다음에 그걸 endList로 받았고, startList를 [1,2,3,...8]로 받아서 비교하는 형식의 코드를 짰는데 이렇게 할 시 상관은 없으나 시간초과가 계속 난다.
ex>
'''
start = / / / 4 5 6 7 8
end = / / 6 8 7 5 2 1
List= 1 2
'''
그래서 스택 하나에 입력하는 수를 꾸준히 넣고, 넣는 도중 top이 입력한 수와 맞으면 pop하도록 하는 형식의 코드를 짜야 한다. 일단 입력을 받은 수는 목표로 하는 수이다. 그 목표보다 stack[-1]이 작으면 stack에 계속 append해주고, 크면 계속 pop해준다.
(코드 짤 때 가장 헷갈릴 수 있는 것이, 목표한 것이 바로 나와버릴 때는 그냥 -해주면 되는데, 내가 append 시켜주다가 목표한 것이 나올 때는 + -를 둘 다 해줘야 하기 때문에 그 두개를 같게 여기는 while 문을 써주면 그게 헷갈렸다ㅠ )
코드에서 하나의 입력을 받았을 때 --이렇게 pop을 두 번 시키는 것은 안되므로 그렇게 되었을 시에는 flag를 False하여 아예 종료시켜버렸다.
'''
망했다...
자꾸 시간초과 난다ㅠㅠㅠ
스택 하나에 입력된 수를 넣었다가 top이 입력한 수와 맞으면 pop하도록 하기
포인트는
바로나왔을 때랑 // 넣고 빠다가 나올 때를 다르게 취급하는 것
'''
import sys
input=sys.stdin.readline
n=int(input())
stack=[0]
PRINT=[]
'''
List=4 3 6 8 7 5 2 1
'''
j=1
for i in range(1,n+1):
flag=True
a=int(input())
if stack[-1]<a: #만약에 stack안에 내가 목표하는 값보다 작은 것밖에 없어
while stack[-1]<=a:
stack.append(j)
PRINT.append('+')
if stack[-1]==a:
PRINT.append('-')
j+=1
stack.pop()
break
else:
j+=1
elif stack[-1]==a: #만약에 내가 딱 목표한 게 딱 있어
PRINT.append('-')
stack.pop()
else:
while stack[-1]>=a:
stack.pop()
PRINT.append('-')
if flag==False:
print('NO')
exit()
flag=False
for i in PRINT:
print(i)
'Koala - 5기 > 기초 알고리즘 스터디' 카테고리의 다른 글
[백준/C++] 14561번 회문 (2) | 2022.01.25 |
---|---|
[백준/python] 7795 먹을것인가 먹힐 것인가 (2) | 2022.01.25 |
[백준/C++] 1371번 가장 많은 글자 (1) | 2022.01.24 |
[백준/python] - 5363번: 요다 (0) | 2022.01.24 |
[백준/python] 2511번 카드놀이 (0) | 2022.01.23 |