[백준 BOJ 10799 silver3 - 쇠막대기] 자료구조 , 스택 C++

백준 쇠막대기

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

10799번: 쇠막대기

 

() 는 레이저, ( 와 ) 는 막대기의 끝을 의미하므로, )가 (을 만나면 스택에서 pop하는 느낌으로 풀어야겠다고 생각은 했다

스택을 이용하면 쉽게 풀 수 있을 것 같은데 처음에 너무 어렵게 생각해서 코드를 이렇게 엄청 복잡하게 짰다..

[시간초과 나는 코드]

string s;
	cin >> s;
	st.push(s[0]);
	int total = 0;

	for (int i = 1; i < s.length(); i++) {
		int top = st.top();

		if (top=='(' && s[i] == ')') {
			st.pop();
			st.push('*');
		}

		if (s[i] == '(') st.push(s[i]);

		if (top == '*' && s[i] == ')') {
			int num_lazer = 0;
			while (true) {
				top = st.top();
				if (top == '*') {
					num_lazer++;
					st.pop();
				}
				else if (top == '(') {
					total += (num_lazer + 1);
					st.pop();
					for (int j = 0; j < num_lazer; j++) {
						st.push('*');
					}
					break;
				}
			}
		}
	}
	cout << total;

처음에 생각했던 아이디어는

() : 레이저이면 스택에서 pop하고, *를 push하여 레이저를 저장하고, 막대기 끝 ) 을 만날때마다 ( 까지 찾으면서 레이저 개수를 세는 것이었다. 그래서 매번 *를 push하고 개수를 세면서 pop하고, 다시 push해야 해서 시간초과가 났다.

 

주어진 조건을 보면 문자열 최대 길이가 100,000 이다. 최악의 경우 N^2이면 너무 오래 걸리게 된다.

 

 

 

[정답 코드]

- 레이저는 pop해주고, 이때 스택 사이즈만큼 더해준다.

- 막대의 끝 일때는 더하기 1을 해준다. 

string s;
	cin >> s;
	st.push(s[0]);
	int total = 0;

	for (int i = 1; i < s.length(); i++) {

		if (s[i] == ')' && s[i - 1] == '(') {
			st.pop();
			total += st.size();
		}
		if (s[i] == '(') st.push(s[i]);
		if (s[i] == ')' && s[i - 1] == ')') {
			st.pop();
			total += 1;
		}

	}
	cout << total;

처음부터 이렇게 생각했어야 하는건데 ㅠㅠ 간단한 풀이가 있는데 생각 못해서 계속 어렵게 풀다 보면 그 늪에 빠져서 다른 풀이를 떠올리는게 어렵다.. 연습을 더 많이 해야겠다