[C/C++] 백준 10799번 - 쇠막대기

10799번: 쇠막대기

이 문제를 처음 접했을 때는 조금 단순하게 생각했다.

()가 연속돼서 입력 됐을 때는 레이저로 인식해서 레이저의 위치를 laser 스택에 집어넣는다.

()가 연속돼서 입력되지 않았을 때는 쇠막대기로 쇠막대기의 위치를 인식해서 iron 스택에 집어넣는다.

그 뒤 레이저에 걸쳐지는 모든 쇠막대기는 잘리기 때문에 걸쳐지지 않는 경우를 넘어가고 나머지 경우의 개수를 모두 셌다.

코드는 다음과 같다. (뒤에 코드가 하나 더 나옴)

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
#define endl '\n'
#define pii pair<int, int>

vector<int> temp;
vector<pii> iron;
vector <pii> laser;
int cnt = 0;

void initInput() {
    string input; cin >> input;
    for (int i = 0; i < input.length(); i++) {
        if (input[i] == '(') {
            temp.push_back(i);
        }
        else {
            int start = temp.back();
            temp.pop_back();
            if (i - start == 1) laser.push_back({start, i}); 
            else iron.push_back({start, i});
        }
    }
}

void solve() {
    cnt = iron.size();

    for (int i = 0; i < laser.size(); i++) {
        auto curLaser = laser[i];
        for (int j = 0; j < iron.size(); j++) {
            auto curIron = iron[j];
            if (curIron.first > curLaser.second || curIron.second < curLaser.first)
                continue;
            cnt++;
        }
    }
    cout << cnt << endl;
}

int main(void)
{
    cout.tie(NULL); cin.tie(NULL); ios_base::sync_with_stdio(false);
    initInput();
    solve();

    return 0;
}

이렇게 제출을 하니 채점하는 시간이 너무 오래걸려서 다른 사람들의 채점 시간을 보니 내 코드보다 훨씬 빨랐다.

그래서 더 좋은 방법이 있는지 다시 생각을 해봤다.

생각을 하다보니 레이저에 대한 스택을 따로 둘 필요가 없었다.

 

새롭게 생각한 방법은 레이저가 입력될 때마다 현재 레이저에 걸쳐지는 쇠막대기의 개수를 세면 된다.

레이저는 스택에 저장하지 않고 쇠막대기만 스택에 저장했기 때문에, 레이저를 만났을 때 스택 요소의 개수를 통해 잘리는 쇠막대기 개수를 알 수 있다.

 

그런데 이렇게 하면 문제가 한가지 있다.

레이저가 자르는 쇠막대기의 개수는 셀 수 있겠지만, 쇠막대기가 잘리고 난 뒤 남은 부분의 개수는 셀 수 없다.

그래서 쇠막대기가 끝나는 부분에서도 개수를 셌다.

#include <iostream>
#include <string>
#include <vector>
using namespace std;
#define endl '\n'

string input;
vector<int> s;
int cnt;

void initInput() {
    cin >> input;
}

void solve() {
    for (int i = 0; i < input.length(); i++) {
        if (input[i] == '(') {
            s.push_back(i);
            if (input[i + 1] == ')') {
                s.pop_back();
                cnt += s.size();
                i++;
            }
        }
        else {
            s.pop_back();
            cnt++;
        }
    }
    cout << cnt << endl;
}

int main(void)
{
    cout.tie(NULL); cin.tie(NULL); ios_base::sync_with_stdio(false);
    initInput();
    solve();

    return 0;
}

이렇게 하니 채점 시간이 단축됐다.