문제 링크
- https://www.acmicpc.net/problem/10799
문제 출처
- 2015 KOI 지역 본선 초등부3, 중등부2
사용 알고리즘
- 스택
시간복잡도
- O(n)
풀이
쇠막대기의 양 끝은 ( 와 ) 로 이루어져있고, 레이저가 지나가는 줄은 () 로 표현됩니다.
이 그림에서 파란 배경의 괄호는 레이저가 지나가는 지점이고, 나머지 괄호는 같은 색끼리 짝입니다.
가장 먼저, 정답을 저장할 변수를 선언한 뒤, 0으로 초기화합니다.
일단 현재 글자가 ( 이면 stack에 넣습니다.
만약 현재 글자가 ) 이면 두 가지의 경우로 나뉘게 됩니다.
- 이전 글자가 ( 이면 이전 글자 + 현재 글자가 () 이 되므로 레이저가 지나가는 자리입니다.
그러므로, stack에서 ( 를 하나 빼주고 현재 위치에 존재하는 쇠막대기의 개수 만큼을 정답을 저장할 변수에 더해줍니다. - 만약 이전 글자가 ( 가 아니라면, 현재 위치에 있는 괄호는 쇠막대기의 오른쪽 끝을 나타내므로 정답을 저장할 변수를 1 증가 시키고(철근은 n번 잘리면 n+1개가 됩니다.),
stack에서 하나를 pop해줍니다.
전체 코드
1 |
|