백준, BOJ 10799번, 쇠막대기 C++ [CPP]

2022.02.25 다시 풀어보았다.

21년 4월에 풀고 거의 1년만이다.

문제다.

 

 

www.acmicpc.net/problem/10799

10799번: 쇠막대기

 

---

 

물론 살펴보면서 규칙을 찾는 것은 많이 어렵지는 않았다.

 

스택에 쌓아가면서 생기는 쇠막대기의 개수를 테스트 케이스와 비교해보면서 규칙을 찾았다.

 

여기서 중요한 것은 스택만 이용하면 안된다.

스택만 이용하면 ()를 처리하는지 멀리떨어져있다가 삭제되어서 ()가 되어서 삭제되는지 알 수 없다.

 

때문에 나는 다른 방법을 이용했다.

문자열 자체를 내 입맛에 맞게 수정하여 다시 이용했다.

 

나의 간과는..  두 번 일을 했다는 것이다. 

우선 나만의 문자열을 다시 만들어서 연산을 수행했기 때문에 시간이 걸렸다.

 

아무튼 다시 요점은 스택에 입력받으면서 ')'를 만났을 때 처리가 중요하다.

즉, 스택을 탐색하면서 문제푸는 것이 아니라.

문자열을 탐색하면서 스택은 보조수단이다.

스택의 ')' 삽입은 이 괄호가 어디서 온지 모른다. ()였는지 (()())의 마지막 괄호였는지 모른다.

하지만 문자열은 변하지 않기 때문에 문자열에서 가리키면 되었다.

 

# 나의 첫 번째 제출

** 코멘트 추가(21.11.25)

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

using namespace std;

int main() {
    string s;
    getline(cin, s);
    stack<int> stk;
    vector<char> v;

    auto t = s.begin();
    auto e = s.end();
    int sum = 0;
	
    
    //다시 말하면 여기서 v에 새로운 문자열을 넣는 대신 계산을 여기서 바로 할 수 있었다.
    while(t != e){
        if (*t == '(' && *(t+1) == ')') {
            v.push_back('.');
            t++;
        }
        else {
            v.push_back(*t);
        }
        t++;
    }

    
	// ex) .(((..)(.).))(.)
    for (char c : v) {
        if (c == '.') {
            sum += (stk.size());
        }
        else if (c == '(') {
            stk.push(c);
        }
        else if (c == ')' && stk.top() == '(') {
            stk.pop();
            sum += 1;
        }
    }

    cout << sum;

}

 

 

#후에 깨달은 뒤의 제출

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

using namespace std;

int main() {
    string s;
    getline(cin, s);
    stack<int> stk;
    vector<char> v;

    auto t = s.begin();
    auto e = s.end();
    int sum = 0;

    while(t != e){
        if (*t == '(' && *(t+1) == ')') {
            sum += stk.size();
            t++;
        }
        else {
            if(*t == ')'){
                stk.pop();
                sum += 1;
            }else{
                stk.push(*t);
            }
        }
        t++;
    }
    cout << sum;
}

 

???

깨달았지만 메모리 대신 시간을 더 먹었다.

 

 

반성할 점

 

스택을 이용하는 것은 좋다.

문자열이 주어질 때 우리가 알고 있는 규칙과 다르다면 원본의 참조할 필요가 있다.

새로운 규칙은 주어진 문자열에서 찾는 것이지 스택에서 찾을 수 없다.

 

---

2022년 짬의 나의 풀이는?

조금 더 시간이 걸렸는데 무리 없이 풀긴했다.

오히려 머리 성장한듯..?

#include <bits/stdc++.h>

using namespace std;



int main(){
    string s;
    cin >> s;
    
    int cnt = 0;
    
    stack<int> stk;
    for(int i = 0; i<s.size(); i++){
        //스택에 비교 대상이 없으면 그냥 넣음
        if(stk.empty()){
            stk.push(s[i]);
        }else{
            //현재 stack에 있는 괄호가 '('일 떼 사실 top에는 이거밖에 없음.
            //정상적인 괄호라면 ')'가 나오면 괄호를 레이저로 만들거나 조각수 증가임.
            if(stk.top() == '('){
                if(s[i] == ')'){
                    //2가지 경우가 있음
                    //레이저로 되는 경우, 그냥 막대기의 끝인경우
                    //i의 범위는 -1 ~15이나 처음 괄호는 '(' 로 시작할 것이므로 가능하지 않음.
                    if(s[i-1] == '('){
                        //레이저
                        //레이저의 경우 top()을 빼고 스택에 남은 stk의 개수만큼 조각수가 늘어남.
                        stk.pop();
                        cnt += stk.size();
                    }else{
                        //막대기의 끝인 경우
                        //막대기의 끝인 경우 그냥 막대기 한조각 늘어남
                        stk.pop();
                        cnt += 1;
                    }
                }
                // s[i] == '(' 일경우 그냥 넣음
                else{
                    stk.push(s[i]);
                }
            }
        }
    }
    
    cout << cnt;
    
    
}