99클럽 코테 스터디 28일차 TIL, 백준 / 스택수열 / 파이썬

🔑 오늘의 학습 키워드 : 스택

🔗 문제링크 https://www.acmicpc.net/problem/1874

 

import sys
input = sys.stdin.readline

n = int(input())
goal = [int(input()) for _ in range (n)]

stack = []
made = []
pointer = 0
answer = []
for i in range (1,n+1):
    stack.append(i)
    answer.append('+')
    while stack and stack[-1] == goal[pointer]:
        made.append(stack.pop())
        answer.append('-')
        pointer += 1
if made == goal:
    for ans in answer:
        print(ans)
else:
    print('NO')

 

🗒️ 공부한 내용 본인의 언어로 정리하기

🤔 문제를 보고 든 생각

간단한 스택 문제구만!

 

⏰ 예상 시간 복잡도 O(N)

제한 사항

첫 줄에 n (1 ≤ n ≤ 100,000)이 주어진다. 둘째 줄부터 n개의 줄에는 수열을 이루는 1이상 n이하의 정수가 하나씩 순서대로 주어진다. 물론 같은 정수가 두 번 나오는 일은 없다.

 

😎 알고리즘 개요

1. 스택 삽입

 

1부터 n까지 스택에 숫자를 집어 넣는다.

answer에 +도 함께 넣는다.

 

2. 스택 비교

 

목표로 하는 수열의 맨 앞과 스택의 맨 위가 같으면 pop하는 연산을 해준다.

그리고 answer 에는 -를 넣는다

 

3. 결과 출력

 

만든 수열 made와 목표 goal이 같으면 answer을 줄바꿈하여 출력하고

 

아니면 못 만드는 경우로써 "NO"를 출력한다.

 

✅ 오늘의 회고

 

- 스택 

 

#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL