백준 10799번 쇠막대기

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

 

아이디어:

1. 어떤 괄호가 레이저인지 구분하는 것이 중요하다.

2. 레이저가 나오기 전 '('의 개수를 기록해놓는다.

3. 레이저가 나온다면 전 '('의 개수만큼 더한다.

4. 레이저가 아닌 ')'가 나온다면 쇠막대기의 마지막 부분으로 1을 더한다.

 

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

int main() {
	int cnt = 0, ans = 0, ch, pch;
	while ((ch = getchar()) != '\n') {
		if (ch == '(') cnt++;
		else cnt--, ans += pch == '(' ? cnt : 1;
		pch = ch;
	}
	printf("%d", ans);
}

 

정답해는 스택을 사용하지않는다.

레이저인지 구분하기 위해 이전 입력 글자를 pch로 기록한다.

쇠막대기 시작 '('이 들어온다면 쇠막대기 토막 개수를 증가시킨다.

')'이 들어온다면 토막 개수를 하나 감소시킨 후, 이전 글자가 '('이라면 레이저이므로 토막 개수만큼 정답을 증가시키고

레이저가 아니라면 쇠막대기의 마지막 토막을 하나 증가시킨다.

 

---

별해

 

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

int main()
{
	stack<int> s;
	string str;

	int cnt = 0;
	cin >> str;
	for (int i = 0; i < str.size(); i++)
	{
		if (str[i] == '(' && str[i + 1] == ')')
		{
			cnt += s.size();
			i++;
		}
		else if (str[i] == '(')
		{
			s.push(i);
		}
		else if (str[i] == ')')
		{
			cnt++;
			s.pop();
		}
	}
	cout << cnt;
}

 

문자열의 i와 i+1번째로 레이저를 구분한다.

 

---

내 풀이

 

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int laser = 0, ans = 0;
	string str;
	cin >> str;
	stack<char> S;

	for (auto i = 0; i < str.length() - 1; i++) {
		if (str[i] == '(' && str[i + 1] == ')') {
			str[i] = 'l';
			str[i + 1] = 'z';
		}
	}
	
	for (auto i : str) {
		switch (i) {
		case '(' :
			ans += 1;
			S.push(i);
			break;
		case ')' :
			S.pop();
			break;
		case 'z' :
			ans += S.size();
			break;
		}
	}

	cout << ans;

	return 0;
}

 

문자열을 순회하면서 레이저 괄호 "()"를 "lz"로 모두 변환한 뒤

다시 한번 문자열을 순회하면서 ans에 직접 더해주는 식으로 풀이했다.