백준 1874번: 스택 수열 (Python)

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

🔹 문제 설명

1부터 N까지의 수를 스택에 오름차순으로 push하고, 필요할 때 pop하여 주어진 수열을 만들어야 한다.

• 수열 생성이 가능하면: 각 연산(+는 push, -는 pop)을 순서대로 출력
• 수열 생성이 불가능하면: NO 출력

---

🔹 내가 작성한 코드

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

# sequence 수열
seq = []
for _ in range(n):
    num = int(sys.stdin.readline())
    seq.append(num)
    
# 수열 스코프
target = 0
# 스택
stack = []
# 출력 결과물 모음
outputs = []

for i in range(1, n+1):
    stack.append(i)
    outputs.append("+")
    # 파이썬 단락평가??
    while len(stack) != 0 and stack[-1] == seq[target]:
        outputs.append("-")
        target += 1
        stack.pop()
        
# 스택이 비워지지 않음
if len(stack) != 0:
    print("NO")
else:
    for out in outputs:
        print(out)

---

🔹 내가 작성한 코드의 특징 및 문제점

✅ 특징

• O(N) 시간 복잡도: 한 번의 반복문으로 수열 처리
• target 인덱스 사용: 입력 수열과 스택 top 비교
• 파이썬 단락 평가 사용: while len(stack) != 0 and ...

❌ 문제점

1. 불필요한 인덱스(target) 접근
   • target 대신 수열을 deque로 처리하면 popleft() 사용 가능
2. 출력 최적화 가능
   • print() 대신 "\n".join(outputs) 또는 sys.stdout.write() 사용으로 속도 향상
3. 조건 단순화 가능
   • 수열을 순회하면서 즉각적인 비교로 더 간단하게 구현할 수 있음

---

🔹 개선된 코드 (더 효율적이고 간결하게)

import sys
from collections import deque

n = int(sys.stdin.readline())
seq = deque(int(sys.stdin.readline()) for _ in range(n))

stack = []
outputs = []
current = 1

while seq:
    target = seq.popleft()
    # target까지 push
    while current <= target:
        stack.append(current)
        outputs.append("+")
        current += 1

    # target과 스택 top이 같으면 pop
    if stack[-1] == target:
        stack.pop()
        outputs.append("-")
    else:
        # 수열 생성 불가
        print("NO")
        sys.exit(0)

# 연산 출력
sys.stdout.write("\n".join(outputs))

---

🔹 개선된 코드의 특징

항목 기존 코드 개선된 코드

시간 복잡도	O(N)	O(N) (동일)
메모리 사용	리스트 (seq), 스택	deque 사용 (더 빠른 pop)
출력 방식	print() 반복 호출	sys.stdout.write() 사용
수열 접근 방식	target 인덱스 추적	deque.popleft()로 즉각 접근
중단 처리	마지막에 스택 검사	sys.exit()로 즉시 종료

---

🔹 실행 예제

✅ 예제 1 (가능한 경우)

입력:

8
4
3
6
8
7
5
2
1

출력:

+
+
+
+
-
-
+
+
-
+
+
-
-
-
-

---

✅ 예제 2 (불가능한 경우)

입력:

5
1
2
5
3
4

출력:

NO

---

🔹 최종 결론 및 요약

1️⃣ 성능 향상: deque를 사용하여 불필요한 인덱스 추적 제거
2️⃣ 코드 간결성: sys.exit()를 사용하여 조건 미충족 시 즉시 종료
3️⃣ 출력 최적화: sys.stdout.write()로 출력 속도 개선
4️⃣ 시간 복잡도: 여전히 **O(N)**로 최적

---

🎯 결론

• 내가 작성한 코드도 충분히 효율적이지만,
• deque 사용, 즉시 종료 처리(sys.exit()), **출력 최적화(sys.stdout.write())**로
  속도와 메모리 측면에서 더욱 향상된 코드를 구현할 수 있음.

🚀 더 빠르고 깔끔한 스택 수열 풀이로 최적의 성능 달성! 🔥✨