-
1874. [Python]스택 수열Python_알고리즘/Silver II 2023. 8. 7. 19:42
1. 문제
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
2. 접근 방법
- 시간 제한: 2초
- 메모리 제한: 128MB
- 스
3. 파이썬 코드
import sys input = sys.stdin.readline N = int(input()) num_list = [] # 초기값 1 value = 1 # N 만큼 만들고 싶은 리스트 값 추가 for _ in range(N): num_list.append(int(input())) # 값들을 저장할 stack 리스트 stack = [] # 기호를 저장할 answer 리스트 answer = [] # 인덱스 번호 index = 0 # push, pop 이 결국엔 N*2 만큼 반복되야 하기 떄문에 반복문 설정 for i in range(N*2): # stack 에 값이 있는 경우 if stack: # stack[-1] 값과 num_list[index] 값이 같은 경우 if stack[-1] == num_list[index]: # answer 에 - 추가 answer.append("-") # stack 에서 값 추출 stack.pop() # index 값 1 증가 index += 1 # 외의 경우 else: # value 값이 N보다 커지는 걸 막음 if value <= N: # stack 에 value 추가 stack.append(value) # value 값 1증가 value += 1 # answer에 + 추가 answer.append("+") # stack 에 값이 없는 경우 else: # value 가 N보다 작으면 if value <= N: # stack, anwer 에 각각 값 추가 후 1 증가 stack.append(value) value += 1 answer.append("+") # 만 약 stack 이 있다면 No 없으면 list 출력 if stack: print("NO") else: for j in answer: print(j)
4. 문제를 풀고난 후 생각
- 값이 들어오면 "+" 를 넣고 나가면 "-" 를 넣는 리스트를 생성하였고, 1~N 까지 숫자가 존재하기 떄문에 반복문의 횟수는 최대 N*2번의 반복문을 통해서 값을 나타낼 수 있었다.
- 값이 들어옴과 동시에 "+"를 리스트에 추가하는 방식으로 리스트 두개를 생성하여 진행하였고, stack 리스트에 값이 없는 경우 stack 에 값을 추가해주는 것으로 반복문을 구성했다.
- 큰 어려움은 없었던 문제였고, 코드의 주석을 통해서 대부분의 내용을 설명했기 떄문에 별도의 설명은 작성하지 않고 어떻게 구현할지 생각했던 것만 작성하였다.
5. 문제를 푸는데 도움이 되는 지식
- 스택
'Python_알고리즘 > Silver II' 카테고리의 다른 글
5397. [Python]키로거 (0) 2023.08.11 1260. [Python]DFS와 BFS (0) 2023.08.08 1541. [Python]잃어버린 괄호 (0) 2023.08.06 1024. [Python]수열의 합 (0) 2023.08.04 1254. [Python]팰린드롬 만들기 (0) 2023.08.04