[백준] 1874. 스택수열

📖 문제

 

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

 

👀 What I Learned

   

   문제점 : 시간이 오래 걸림 ( 3304ms )

   원인 : if, elif 등 분기 구간이 많아 연산량이 많음

   

   연산량을 낭비하지 않도록 for, while 문 적절히 활용하기. 어떻게 처리할지 미리 손코딩으로 구조 짜보기

📖 풀이 과정

# N값 입력
N = int(input())

target_list = []

for _ in range(N): # 타겟 순열 입력
    target_list.append(int(input()))

idx = 0
stack = []
i = 1
answer = []

while True:
    if not stack: # 스택이 비어있는 경우
        stack.append(i) # push 연산
        i += 1 # 오름차순이므로 1씩 증가
        answer.append("+")
        
    elif stack[-1] == target_list[0]: # 스택의 top값 = 타겟 순열 값
        stack.pop(-1) # pop 연산
        target_list.pop(0) # 순열리스트에서도 제거
        answer.append("-")
    elif stack[-1] > target_list[0]: # 스택의 top > target값 인 경우 
        print("NO") # 불가능하므로 NO 출력
        break
    else: # stack에 값이 있고 & 타겟 순열값은 아닌 경우
        stack.append(i) # push 연산
        i += 1
        answer.append("+")

    if not target_list : # 타겟값 다 맞췄으면
        for num in answer: # 출력
            print(num, end='\n')
        break

 

📖 Solution

 

- 입력과 비교를 한번에 처리함

- 순열을 차례로 입력하면서 필요한 만큼만 연산하므로 시간 단축 가능 (192ms)

import sys
n = int(sys.stdin.readline())
stack = []
answer = []
flag = 0
cur = 1

for i in range(n):
    num = int(sys.stdin.readline())
    while cur <= num: # 입력한 수 만날 때 까지 오름차순으로 push
        stack.append(cur)
        answer.append("+")
        cur += 1
        # 입력한 수를 만나면 while문 탈출.
        # cur = num일때까지 while문으로 스택을 쌓는다.
    
    if stack[-1] == num: # stack의 Top이 입력한 값과 같다면
        stack.pop() # stack의 top을 꺼내 수열을 만들어 준다.
        answer.append("-")
    else:
        print("NO")
        flag = 1
        break
        # stack의 top이 입력한 수가 아니면 주어진 스택을 만들 수 없다.
        # 스택은 무조건 오름차순으로 push되기 때문에 top이 num보다 크면
        # 원하는 순열을 만들 수 없다.
if flag == 0: # 순열을 만들 수 있는 경우
    for i in answer:
        print(i)