문제: https://www.acmicpc.net/problem/10799
접근방식
레이저 ()는 그 시점에 열려 있는 막대 (를 모두 자르므로, 열려 있는 막대의 길이만큼 조각 수를 더한다. 하나의 막대가 2개의 레이저에 의해 잘린다면, 총 3개의 조각이 생기게 되므로 막대의 끝인 )을 만나면 조각 수를 1 추가한다.
이를 스택으로 구현하면 다음과 같이 작성할 수 있다.
(이라면 스택에 push한다.)이라면 두 가지 케이스 중 하나이다.- 레이저인 경우 (이전 문자가
(인 경우)- 레이저의 시작
(을 pop하고, 레이저가 지나가는 막대는 막대 시작(의 개수이므로 stack의 길이만큼 count 증가
- 레이저의 시작
- 막대의 끝인 경우 (이전 문자가
)인 경우)- 막대의 시작
(을 pop 하고 count를 1 증가
- 막대의 시작
- 레이저인 경우 (이전 문자가
구현
const fs = require("fs")
const str = fs.readFileSync("/dev/stdin").toString().trim()
const stack = []
let count = 0
for (let i = 0; i < str.length; i++) {
if (str[i] === '(') {
stack.push('(')
} else {
stack.pop()
count += str[i - 1] === '(' ? stack.length : 1
}
}
console.log(count)단계별 시뮬레이션
input: ()(((()())(())()))(())
| 단계 | 문자 | 이전문자 | 스택 상태 | 설명 | 조각 수 |
|---|---|---|---|---|---|
| 1 | ( | null | ( | 막대 시작 | 0 |
| 2 | ) | ( | 레이저 → 스택 길이 0 → +0 | 0 | |
| 3 | ( | ) | ( | 막대 시작 | 0 |
| 4 | ( | ( | (( | 막대 시작 | 0 |
| 5 | ( | ( | ((( | 막대 시작 | 0 |
| 6 | ( | ( | (((( | 막대 시작 | 0 |
| 7 | ) | ( | ((( | 레이저 → 스택 길이 3 → +3 | 3 |
| 8 | ( | ) | (((( | 막대 시작 | 3 |
| 9 | ) | ( | ((( | 레이저 → 스택 길이 3 → +3 | 6 |
| 10 | ) | ) | (( | 막대 끝 → +1 | 7 |
| 11 | ( | ) | ((( | 막대 시작 | 7 |
| 12 | ( | ( | (((( | 막대 시작 | 7 |
| 13 | ) | ( | ((( | 레이저 → 스택 길이 3 → +3 | 10 |
| 14 | ) | ) | (( | 막대 끝 → +1 | 11 |
| 15 | ( | ) | ((( | 막대 시작 | 11 |
| 16 | ) | ( | (( | 레이저 → 스택 길이 2 → +2 | 13 |
| 17 | ) | ) | ( | 막대 끝 → +1 | 14 |
| 18 | ) | ) | 막대 끝 → +1 | 15 | |
| 19 | ( | ) | ( | 막대 시작 | 15 |
| 20 | ( | ( | (( | 막대 시작 | 15 |
| 21 | ) | ( | ( | 레이저 → 스택 길이 1 → +1 | 16 |
| 22 | ) | ) | 막대 끝 → +1 | 17 |
trim()
입력 끝에 개행문자 \n가 붙어있어 입력 값에 trim을 적용하지 않으면 오답으로 처리됨...
https://deun.dev