[백준/c++] 10799 - 쇠막대기

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

10799번: 쇠막대기

---

1) 풀이

얼핏 보면 어려워보일 수 있지만..!

정답 비율이 꽤 높은 다소 단순한 문제 😆

 

이 문제에서는 쇠막대기와 레이저 모두 ( 와 )를 이용하여 나타낸다.

하지만, 쇠막대기와 레이저를 구분하는 방법은 꽤 단순하다.

이전 문자열을 확인하여, 이전 문자열이 ( 라면 레이저, 아니라면 쇠막대기라고 생각해주면 된다.

 

이것을 기억하고, 문자열의 문자 하나하나를 읽어가면서,

( 괄호를 스택에 넣고 )를 만날때마다 레이저, 쇠막대기를 구분해서 처리해주면 된다.

(기본적인 괄호 짝 지어주는 알고리즘은 아래 글을 참고하면 좋을듯 하다)

2021.03.04 - [알고리즘 코테준비/백준] - [백준/c++] 4949 - 균형잡힌 세상

그렇다면 나눠지는 쇠막대기 카운팅은 어떻게 하면 좋을까?

그것은 바로, 스택에 남아있는 ( 의 수, 즉 스택의 길이를 고려하면 된다. 

위의 그림은, 문제의 예시 그림의 일부를 잘라온 것이다.

( () () ) 의 문자열만으로 설명을 해보자면, 지금 () 모양의 레이저는 총 2개, 잘라진 쇠막대기는 총 3개이다.

위 그림에 '자른다'의 개념을 더 확실하게 설명하기 위해 선을 그려보았다.

 

 

별로 상태는 안 좋지만.. 감안하고 봅시다 ㅠ ㅠ

우선, 쇠막대기는 첫번째 레이저, 즉 첫번째 빨간색 줄에서 한 번 잘린다.

그렇게 되면 총 쇠막대기의 수는 2개지만, 이 설명에서 우리는 쇠막대기의 수를

잘려나온 부분만을 고려할 것이므로 첫번째 빨간색 줄에서 잘린 쇠막대기 조각은 하나가 된다.

역시 두번째 빨간색 줄(레이저)에서 쇠막대기가 잘리고 잘려나온 쇠막대기는 총 2개가 된다.

그리고 쇠막대기의 끝을 나타내는 ) 가 나오는데, 우리는 이 문제에서 쇠막대기의 끝 또한 '잘린다'라는 개념으로

이해하면 문제를 쉽게 풀 수 있다.

즉, 진짜 잘리는 것은 저 빨간색 두줄이지만, 실질적으로 조각을 카운팅하기 위해서는

쇠막대기 끝부분도 우리가 쇠막대기를 자르는 것처럼 생각하고 한조각을 카운팅해주면

총 쇠막대기 수를 쉽게 구할 수 있다!

(쇠막대기의 끝은, 위에서 레이저와 쇠막대기를 구분하는 방법으로 알 수 있다!)

 

이것을 모두 이해한다면, 굉장히 쉽게 풀리는 문제이다!

2) 최종 소스코드

#include <bits/stdc++.h>
using namespace std;
stack<char>st;
string s;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int ans = 0; // 총 쇠막대기 수
	cin >> s;

	for (int i = 0; i < s.size();i++) {
		if (s[i] == '(') {
			st.push(s[i]); 
		}
		else if (s[i] == ')') {
			if (s[i - 1] == '(') { //레이저일떄
				st.pop();
				if (st.size() != 0) {//쇠막대기는 아무것도 없고 레이저만 있는 상태가 아니라면
					ans += st.size(); //현재 들어있는 쇠막대기 수
			}
			else if (s[i - 1] != '(') { //쇠막대기일때
				st.pop();
				ans += 1; //마지막 조각 더해준다
			}
		}
	}
	cout << ans << '\n';
}

3) 참고자료

blog.encrypted.gg/936?category=773649