[Python]백준 BaekJoon.AC 1874 : 스택 수열(스택)

 

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

1874번: 스택 수열

 

 

빙 돌아온 문제였다.

최종적인 답안은 짧은 편인데, 원초적인 코드는 굉장히 길었다.

 

 

에라 모르겠다 싶어 제출한 코드가 의외로 정답처리 됐고, 아주 깔끔한 답안은 분명 아닐 거라 생각하고 수정보완 해줬다.

 

그냥 넘어갈 수도 있었는데 굳이 코드를 처음부터 다시 짰고, 그걸 더 수정했다.

 

 

지금 생각해보면 잘한 일이었다.

축약에 있어 깨달음도 얻었고, 다시 짚어야 할 점을 상기시킨 기회가 됐다.

 

 

<지저분한 코드, 비추천>

N = int(input())
box = [] # list pop() = O(1)
ans = []

ip = int(input())

for n in range(1, N+1):

    box.append(n)  # O(1)
    ans.append("+")

    if n == ip:
        box.pop()
        ans.append("-")
        if len(ans) == 2 * N:
            break
        ip = int(input())
    else:
        continue

    while True:
        try:
            if box[-1] == ip:
                box.pop()
                ans.append("-")
                if len(ans) == 2 * N:
                    break
                ip = int(input())
            else:
                break
        except:
            break

if len(ans) == 2 * N:
    for a in ans:
        print(a)
else:
    print("NO")

 

 

 

정답 후 다듬은 코드인데도 꽤 길다.

 

내 코드는 시간이 4초로 찍혔는데 다른 사람들의 코드는 0.2초가 채 안걸리더라.

단단히 문제가 있는건가, 생각하며 코드 비교에 돌입했다.

 

 

 

그런데 가만보니 사소한 부분을 놓치고 있었다.

100,000개라 무시했던 입력수를 간과하지 않아야겠으며,,, sys.stdin.readline()을 더 적극적으로 사용해야겠다.

 

 

또한 코드를 더 넓게 보는 시야가 중요!

필요하지 않은 코드도 사용하고 있었다.

합쳐도 될 연산을 굳이 나눠서 계산해줬다.

너무 내 기준으로 문제풀듯 코딩했고, 컴퓨터는 순차적이기만 하다면 엉킨 문제도 척척 풀 수 있는 아이였음을... 잊지 말아야겠다.

 

 

 

간단한 수정만으로도 0.2초대의 시간을 나타냈다. (이게 다 input 때문이었다..)

 

 

 

 

import sys

N = int(input())
arr = [int(sys.stdin.readline()) for b in range(N)]
box = [] # list pop() = O(1)
ans = []
index = 0

for n in range(1, N+1):
    box.append(n)  # O(1)
    ans.append("+")

    while box and box[-1] == arr[index]:
        box.pop()
        ans.append("-")
        index = index + 1

if not box:  #len(ans) == 2 * N
    for a in ans:
        print(a)
else:
    print("NO")