[GDSC Week2-2] 백준 10828번:: 스택 (C++)

 

 

* 생각한 아이디어 및 문제 풀이

1. 전체를 string으로 받고 각각 char stack으로 넣기로 했다.
2. 괄호 (~)가 하나의 막대인 것이므로 '('가 들어오면 스택에 넣는다.
3. 그리고 다음에 들어오는 ')'로 비교를 한다. 만약 바로 '('가 있었다면 이는 레이저이므로 기존 stack 사이즈만큼 새 조각이 생기는 것을 이용한다.
4. 만약 레이저가 아니면, 그냥 쇠막대기 이므로 쇠막대기 개수 +1만 한다.

 

* 코드

#include <iostream>
#include <string>
#include <stack>
using namespace std;

int main(){
    ios::sync_with_stdio(false); 
    cin.tie(NULL); cout.tie(NULL);
    
    stack<char> s;
    int bar = 0;
    string input;
    cin >> input;
    
    for(int i=0; i<input.length(); i++){
        if(input[i] == '('){
            s.push('(');
        }
        else if (input[i] == ')'){
            if(input[i-1] == '('){
                bar+=s.size()-1;
                s.pop();
            } else{
                bar++;
                s.pop();
            }
        }
    }
    cout << bar;
}

 

 

* 회고 :

 

문제 자체를 이해하기가 좀 헷갈려서 참고 링크를 보고 이해를 했던 점이 아쉽다.

다시 정리를 해보자면, ()는 레이저 즉 커팅하는 것, (~)는 쇠막대기 이다.

따라서 if의 경우(레이저일 때)에서는 bar의 개수에서 스택의 사이즈를 더하고 -1을 해준다.

레이저인 경우에 스택의 사이즈만큼 새로운 조각이 생긴다는 것을 의미한다.

여기서 -1은 else 경우에서 막대기 연산을 해주므로 해당하는 막대기 -1을 해준다.

else 경우 (쇠막대기 체크하는 부분)에서 bar의 개수 ++를 해주고, 그 막대기의 처리가 끝났으니 pop을 해준다.

이 그림에서 파란색 부분이 if 부분의 연산, 보라색 부분이 else 부분의 연산이라고 할 수 있겠다.

 

다른 코드중에 stack을 사용하지 않고 괄호로만 체크하는 것도 있어서 제출해보았으나 메모리는 똑같이 사용되었다.

#include <iostream>
#include <string>
using namespace std;

int main(void) {
	string str;
	cin >> str;	// 문자열 입력

	int sum = 0;  // 총 막대의 개수
	int cnt = 0;
	int prev = 0;	// 만약 전에 열린괄호였으면 1, 닫힌괄호였으면 0
	for (int i = 0; i < str.size(); i++) {
		if (str[i] == '(') {	// 열린 괄호 등장
			cnt++;	// 새로운 막대가 하나 깔림
			prev = 1; // 다음 반복문에서는 전 괄호가 열린 괄호이다
		}
		else {	// 닫힌 괄호 등장
			if (prev == 1) {	// 바로 전이 열린괄호라는 것은 레이저라는 뜻
				cnt--;	// 레이저가 자르는 막대의 수는 cnt에서 1 빼야됨, 전에 레이저인 (에서도 ++해줬으므로
				sum += cnt;	// 레이저가 자르는 막대의 개수를 결과에 +=
			}
			else {	// 레이저가 아니라 그냥 막대의 끝
				sum++;	// 초기 막대들을 이런식으로 하나씩 세줌
				cnt--;	// 아래 깔린 막대가 하나 사라짐
			}
			prev = 0; // 다음 반복문에서는 전 괄호가 닫힌 괄호이다
		}
	}
	cout << sum << endl;	// 결과 출력

	return 0;
}

 

 

* 문제 링크 : https://www.acmicpc.net/problem/10799

10799번: 쇠막대기

 

* 참고 링크 :
https://tunafish78.tistory.com/100
https://j-shine.github.io/baekjoon-algorithm/2020/07/18/baekjoon-10799.html

[백준 10799] 쇠막대기

[백준 10799번] 쇠막대기