✅ stack

문제

링크

풀이

1. 문제 접근

괄호 모양에 따라 막대기인지, 레이저인지 구분해야 한다.
'(' 가 나온뒤 바로 ')' 가 나오면 레이저이고
')'가 나온뒤 ')'가 나오면 막대기가 끝나는 지점이다.

레이저가 나오면 그때 존재하는 막대기들은 모두 한번씩 짤린다.

2. 자료구조 선택과 그 이유

레이저, 막대기를 구분할 필요가 있긴 하지만
둘 다 열린괄호와 열린괄호 이전 가장 최근에 나온 닫힌괄호의 짝으로 판단하기 때문에 stack을 사용하기로 함

3. 문제 해결 로직 (풀이법)

막대기 하나를 레이저로 두번 짜르면 3등분이 된다. 즉,
1. 막대기가 추가될 때 +1 를 해주고
2. 레이저가 나올 때마다 현재 stack에 존재하는 막대기의 개수를 더 해준다.

의사코드

cin >> str // str : 한 줄에 쇠막대기와 레이저의 배치를 나타내는 괄호 표현

for(i : 0 ~ str.length){
	if(str[i] == '(') {
    	stack.push('(')
    	cnt ++ // 막대기가 추가될 때 +1
        isLaser = true 
    }
    if(str[i] == ')'){
    	if(isLaser == true) {
        	cnt-- // 레이저인지 모르고 추가한 막대기 다시 빼줌
            cnt += stack.size // 레이저가 나올 때마다 현재 stack에 존재하는 막대기의 개수를 더 해준다.
            stack.pop
        }
        else{
       		stack.pop
        }
        isLaser = false
    }
}

cout << cnt

4. 시간 복잡도 분석

O(N)

5. 문제에서 중요한 부분

괄호쌍을 찾는 문제라 stack을 떠올리기는 어렵지 않았다.
다만 레이저가 나왔을 때를 판별하는 것과
레이저 나올 때 아직 끝나지 않은 막대기 개수를 더해주고 특히 막대기가 처음 추가될 때 +1을 해줘야 한다는거..