[10799] 쇠막대기 - 스택 ★★☆☆ / 복습 ○

[ 문제 ] : https://www.acmicpc.net/problem/10799

10799번: 쇠막대기

---

 

[ 문제 접근 ]

 

괄호가 나왔으니 스택 문제라는건 쉽게 예상 가능.

 

( 나오면 스택에 집어 넣고

 

) 나오면 스택에서 빼는 전형적인 문제이겠거니 하고 접근.

 

문제를 읽고 한번에 이해 되지 않아서 공책에다가 시뮬레이션을 한번 해봄으로서 이해 할 수 있었다.

 

결론 적으로 스택 문제라기 보다는 구현 문제에 가까웠던것 같다.

( 실제로 스택을 사용하지 않고 풀었다.)

 

처음 풀었을때는 스택을 사용하였는데 구현하다 보니 스택이 필요 없어도 되겠다 싶어서 주석 처리 해줬다. 

---

[ 과정 ]

 

스택 문제라고 인식

-> 입력을 모두 받은 뒤 스택 위에서부터 빼면서 결정할 것인가? 입력을 받으면서 결정할 것인가?

-> 빼면서 해도 괄호를 닫을때 멀리 있는 괄호를 닫은것인가 바로 앞 괄호를 닫을것인가에 대한 판단은 바로 전 입력을 참고해야하기에 그냥 입력을 받으면서 로직 처리하는게 좋다고 판단

-> 시뮬레이션 해본 결과, num 이라는 변수와 sum이라는 변수를 두어 레이저로 짤릴때마다 값을 조작해야됨을 인지.

 

 

스택의 문제의 응용 대부분은 멀리 있는 괄호와 가까이 있는 괄호를 구분할 수 있는지가 관건이다.

 

---

[ 스택 사용하지 않은 코드 ]

 

#include<iostream>
#include<vector>
#include<string>
#include<stack>

using std::cin; using std::cout;
using std::vector;

int main() {
	std::ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	std::string str;
	
	int sum = 0;  // 레이저에 짤렸을때 누적 정답.
	int num = 0;  // 막대기 하나씩 늘어갈때마다 늘려줄 변수.
	std::stack<char> st;
    
	cin >> str;
	for (int i = 0; i < str.length(); i++) {
		if (str[i] == '(') {
			//st.push('(');
			num += 1;
		}
		else {
			if ( str[i-1] == '(') { //!st.empty() &&
				num -= 1;
				sum += num;
				//st.pop();
			}
			else {
				sum += 1;
				num -= 1;
			}
		}
	}
	cout << sum;
	return 0;
}

 

[ 스택 사용한 코드 ]

 

using namespace std;
string s;
int ans = 0;
stack<char> st;

int main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> s;
  int sz = s.length();
  for (int i = 0; i < sz; i++) {
    if (s[i]=='(')
      st.push(s[i]);
    else {
      if (s[i-1] == '(') { // 바로 전이 ( 로 => 레이저일 경우
        st.pop(); // 앞에서 막대라고 착각하고 stack에 s[i]를 넣었으므로 pop
        ans+=st.size(); // 막대의 개수만큼 ans에 추가
      }
      else { // 막대의 끝일 경우
        st.pop();  // 막대의 개수를 1 감소
        ans++; // 막대 1개가 절단된 것과 동일한 상황이므로 ans에 1 추가
      }
    }
  }
  cout << ans << "\n";
  return 0;
}

---

[ Key Point ]

 

👉 막대의 개수인 num 변수를 사용해야겠다는 생각을 할 수 있어야한다.

 

---

[ 다른 사람 풀이 ]

 

ref :: https://hsp1116.tistory.com/29