S2 1874. 스택 수열

문제 보기 :  1874번: 스택 수열

---

문제

• 정답률 : 38%

---

작성 코드

num = int(input())
ls = [int(input()) for _ in range(num)]

sub = [] # 스택
answer = [] #"+", "-" 저장
c = False #"No" 출력 여부 확인

a = 1
for _ in range(num):
    b = ls.pop(0) #4
    if not sub:
        sub.append(a)
        a += 1
        answer.append("+")

    if sub[-1]!=b: 
        if a<=b: 
            sub += [i for i in range(a,b)]
            answer += ["+"]*(b-a+1)
            answer += ["-"]
            a = b+1
        else:
            c = True
            break
    else:
        sub.pop()
        answer.append("-")

if c:
    print("NO")
else:
    print(*answer,sep="\n")

---

풀이

스택, 큐는 잘 알려져있는 자료구조고 이 문제는 쉬울 것이라 생각했는데 정답률은 생각보다 낮은 문제라 걱정과 함께 시작한 문제다.

내가 마주했던 이슈는 '시간초과'였는데, 아무래도 100,000개까지 입력이 가능하다보니 이중 for,while문을 사용하게 되면 시간초과가 발생하는 것 같다.

그래서 나는 for문으로만 작성하고, 당장 나와야하는 값인 b와 현재 값인 a를 비교해서 "+"와 "-"를 적당히 조절하는 방식으로 풀이했다.

NO를 출력하는 케이스도 별도로 만들어야해서 for문 안에 바로 print("+")를 두진 않았다.

아, 그리고 테스트 케이스가 길어서 그런가 제출하고 나서 채점시간이 꽤 길어서 쫄리는 문제였다..