[백준] 1874번 파이썬(Python)

문제

스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다.

1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라.

입력

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

출력

입력된 수열을 만들기 위해 필요한 연산을 한 줄에 한 개씩 출력한다. push연산은 +로, pop 연산은 -로 표현하도록 한다. 불가능한 경우 NO를 출력한다.

---

'오답 코드'

import sys

n = int(sys.stdin.readline())

order = [] # 오름차순 스택
stack = [] # 입력받은 리스트
sequence = [] # 연산 리스트

for _ in range(n):
    stack.append(int(sys.stdin.readline()))

for i in range(n):
    if i == 0:
        for j in range(stack[i]):
            order.append(j+1)
            sequence.append("+") #push
        order.pop()
        sequence.append("-") #pop
    else:
        if stack[i-1] > stack[i]:
            if order[-1] == stack[i]:
                order.pop()
                sequence.append("-") #pop
            else:
                # 뒤에 남은 숫자까지 삭제하면 break
                if order[-1] in stack[i+1:]:
                    print("NO")
                    break
                else:
                    for _ in range(stack[i-1] - stack[i]):
                        order.pop()
                        sequence.append("-") #pop

        elif stack[i-1] < stack[i]:
            cnt = max(stack[:i])
            for j in range(cnt+1, stack[i]+1):
                order.append(j)
                sequence.append("+") #push
            order.pop()
            sequence.append("-") #pop

else:
    for i in sequence:
        print(i)

# print("현재 스택 상태 :", order)

백준 예제 입력 시 출력이 모두 같게 나오는데 계속 시간 초과 오류가 뜬다.

아마 다른 예제를 입력했을 때 출력이 다르게 나오나보다...

근데 뭐가 문제인지 모르겠다 🤯

 

'문제 해결 아이디어'

스택에 push하는 순서는 반드시 오름차순이다!

 

'정답 코드'

import sys

n = int(sys.stdin.readline())

stack = [] # 입력받은 리스트
sequence = [] # 연산 리스트

cnt = 1

for _ in range(n):
    num = int(sys.stdin.readline().rstrip())

    # push
    while cnt <= num:
        stack.append(cnt)
        sequence.append("+")
        cnt += 1

    # pop
    if stack[-1] == num:
        stack.pop()
        sequence.append("-")
    else:
        print("NO")
        break

else:
    for i in sequence:
        print(i)

 

'복기하기'

- break문 : while, for문을 사용하는 반복문에서 'break'를 사용하면 반복문 전체를 빠져나오게 됨

- for-else문 : for문이 break 등으로 중간에 빠져나오지 않고 끝까지 실행됐을 경우 else문이 실행되는 방식

 

'돌아보며'

예제 입력과 출력에 초점을 맞추지 말고, 즉 노가다식 코딩 하지말고 단순하게 풀려고 노력하자...