개미의 개열시미 프로그래밍

[알고리즘] 백준1874 스택 수열 - 파이썬 본문

알고리즘/그리디 & 구현

[알고리즘] 백준1874 스택 수열 - 파이썬

YunHyeok 2021. 11. 2. 23:02
728x90
반응형

https://www.acmicpc.net/problem/1874

 

1874번: 스택 수열

1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다.

www.acmicpc.net

 

[풀이 코드] 

n = int(input())

count = 1
stack = []
result = []

for i in range(n): # 데이터 갯수만큼 반복
    data = int(input())
    while count <= data: # 입력 받은 데이터에 도달할 때까지 삽입
        stack.append(count)
        count += 1
        result.append('+')
    if stack[-1] == data: # 스택의 최상위 원소가 데이터와 같을 때 출력
        stack.pop()
        result.append('-')
    else: # 불가능한 경우
        print("NO")
        exit(0)

print('\n'.join(result)) # 가능한 경우

- 문제 유형은 그리디, 스택!

- 시간내에 문제를 해결하지 못해서 결국 나동빈 강사님의 답을 보고 이해했다..

 

코딩 테스트를 봤을 때 이런 비슷한 문제 유형을 본 적이 있는데 확실히 기초가 부족해서 그런지 오래 걸렸던 기억이 난다.  이제 다음 코테 볼 땐 십 분 만에 풀어버리기로..

 

728x90
반응형
Comments