2. 쇠막대기(스택)_python

전체코드

import sys
sys.stdin=open("C:\\input.txt",'rt')
# input : ()(((()())(())()))(())  # 결과 : 17

s = input()
stack = []
cnt =0

for i in range(len(s)):
    #열린 괄호
    if s[i] =='(':
        stack.append(s[i])
    #닫는 괄호
    else:
        stack.pop()

        # 바로 앞이 열린 괄호일때
        if s[i-1] == '(':
            cnt += len(stack)
        # 바로 앞이 닫힌 괄호일때
        else:
            cnt+=1

print(cnt)

 

---

괄호 문자열 ()(((()())(())()))(())는 쇠막대기와 레이저를 나타냄.

• 레이저: () (열린 괄호 ( 다음에 바로 닫힌 )이 나오는 경우)
• 쇠막대기: 레이저를 만나면 조각이 늘어남

이 코드는 레이저가 막대기를 자를 때 조각 개수를 세는 알고리즘이야.

---

📌 코드 분석

 

s = input() # 입력 받기 stack = [] # 스택 (쇠막대기의 열린 괄호를 저장) cnt = 0 # 조각 개수

• s: 입력 문자열
• stack: 열린 괄호를 저장하는 스택
• cnt: 잘린 조각 개수를 저장하는 변수

---

🔄 for문 동작 과정

 

for i in range(len(s)): # 문자열 길이만큼 반복

문자열을 한 글자씩 확인하면서 처리!

---

✅ 열린 괄호 ( 일 때 → 스택에 추가

 

if s[i] == '(': stack.append(s[i])

• 열린 괄호가 나오면 쇠막대기의 시작이므로 스택에 추가

---

✅ 닫는 괄호 ) 일 때 → 스택에서 꺼냄

 

else: stack.pop() # 스택에서 '(' 제거 (쇠막대기의 끝 or 레이저)

• 닫힌 괄호가 나오면 쇠막대기 하나가 끝나거나 레이저임
• 무조건 stack.pop() → 이전에 열린 (을 제거

---

✅ () → 레이저일 경우

 

if s[i-1] == '(': cnt += len(stack) # 현재 남아 있는 쇠막대기의 개수만큼 추가

• 바로 앞 글자가 (이면 레이저! (())
• 레이저를 만나면 현재 스택에 있는 쇠막대기의 개수만큼 조각 추가

예제:

(()(((()())(())()))(())) ↑ ↑↑ ↑ ↑ 레이저가 있는 곳 (이전 문자가 '(')

 

• 이 위치에서 stack에 있는 쇠막대기 개수만큼 조각이 생김!

---

✅ 쇠막대기 끝 ()) → 한 조각 추가)

 

else: cnt += 1 # 막대기의 끝 부분 → 1조각 추가

• ()가 아니라 단순히 ))일 경우 → 쇠막대기의 끝
• 이 경우 막대기의 마지막 조각 1개 추가

---

📝 예제 실행 과정

입력:

 

()(((()())(())()))(())

과정:

i문자동작stackcnt

0	(	스택 추가	[()]	0
1	)	레이저	[]	0 + 0 = 0
2	(	스택 추가	[()]	0
3	(	스택 추가	[(, ()]	0
4	(	스택 추가	[(, (, ()]	0
5	(	스택 추가	[(, (, (, ()]	0
6	)	레이저	[(, (, ()]	3 + 0 = 3
7	(	스택 추가	[(, (, (, ()]	3
8	)	막대기 끝	[(, (, ()]	3 + 1 = 4
9	)	막대기 끝	[(, ()]	4 + 1 = 5
10	(	스택 추가	[(, (, ()]	5
11	(	스택 추가	[(, (, (, ()]	5
12	)	레이저	[(, (, ()]	5 + 3 = 8
13	)	막대기 끝	[(, ()]	8 + 1 = 9
14	)	막대기 끝	[()]	9 + 1 = 10
15	(	스택 추가	[(, ()]	10
16	)	레이저	[()]	10 + 1 = 11
17	)	막대기 끝	[]	11 + 1 = 12

최종 결과:

17

---

🎯 코드 핵심 요약

1. ( → 스택에 추가 (쇠막대기 시작)
2. )
   • 앞이 ( (()) → 레이저
     → 현재 스택 길이(=현재 남아 있는 쇠막대기 개수)만큼 cnt 증가
   • 앞이 ) ())) → 쇠막대기 끝
     → cnt에 1 추가

---

🚀 최적화된 코드

이 코드는 스택을 활용한 O(n) 시간 복잡도 알고리즘이야!
(문자열을 한 번만 스캔하므로 매우 빠름)