문제

---

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

📌 문제 요약

괄호로 표현된 쇠막대기와 레이저가 주어진다.

• (는 쇠막대기 시작

• )는 쇠막대기 끝

• 단, ()는 레이저로 간주
  레이저가 쇠막대기를 자르면 그 개수만큼 조각이 생긴다.

풀이

---

⚠️ 시간초과 코드 분석

inputs = input()

index = -1
left = []
laser = []
partisions = 0

for i in inputs:
    index += 1

    if i == "(":
        left.append(index)
        continue

    if index - left[-1] == 1:
        index -= 1
        laser.append(index)
        left.pop()
    else:
        start = left.pop()
        end = index
        laserCnt = 0

        for j in laser:
            if start <= j and j <= end:
                laserCnt += 1
        
        partisions += laserCnt+1

print(partisions)

❗ 이 코드가 시간 초과 나는 이유:

1. laser 리스트에 모든 레이저의 위치를 저장하고 있음.

2. 쇠막대기 하나가 끝날 때마다, 그 레이저 리스트를 순회하며 검사함 → O(N^2)

   • 특히 입력 길이가 수천~수만일 경우 매번 for문 안에서 또 for문이 도는 셈.

3. index -= 1 같은 조작은 index 흐름을 꼬이게 하므로 추천되지 않음.

✅ 통과한 정답 코드 (스택 기반, O(N))

---

sticks = input()
stack = []
result = 0

for i in range(len(sticks)):
    if sticks[i] == '(':
        stack.append('(')
    else:
        stack.pop()
        if sticks[i - 1] == '(':  # 레이저인 경우
            result += len(stack)
        else:  # 막대기 끝
            result += 1

print(result)

💡 핵심 아이디어:

• 여는 괄호(는 스택에 push

• 닫는 괄호)를 만나면:

  • 바로 앞이 ( → 레이저 → 현재 열린 막대기 수만큼 자름
  • 아니면 → 막대기 끝 → 조각 1개 더하기

✅ 시간 복잡도:

• 문자열 1회 순회 + 스택 연산 → O(N)
• 불필요한 리스트 저장, 중첩 루프 없음

🧠 두 코드 비교 요약

---

항목	시간초과 코드	정답 코드
시간복잡도	O(N^2)	O(N)
레이저 추적 방식	laser 리스트에 저장 후 매번 탐색	인접 괄호를 이용한 즉시 판별
주요 병목	for j in laser: 반복	없음
실용성	대입 테스트는 통과, 실전에서는 실패	실전용 성능 보장

📝 마무리

---

이 문제의 핵심은 스택을 적절히 활용하면서 레이저와 막대기를 구분하는 것이다.
특히 중첩된 괄호 구조에서 시간복잡도 이슈가 생기지 않도록 즉시 판단하고 처리하는 로직이 중요하다.

✔ 교훈:

괄호 짝맞춤 문제는 대부분 스택이 해법!
불필요한 반복문이 있다면, 더 효율적인 자료구조 접근을 고민해보자.