10799 쇠막대기

10799. 쇠막대기 / c++ / Silver2 / 26분

문제

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

1. 괄호로 이루어진 문자열이 주어진다.
2. () 딱 붙어있는 괄호는 레이저
3. 레이저로 잘라진 막대기의 총 갯수는?

접근 방식

자료구조, 스택

1. 괄호는 일단 스택이라고 생각해본다.
2. ’(‘ 열린 괄호가 나오면 스택에 추가한다.
3. ’)’ 닫힌 괄호가 나오면 두가지 경우로 나눈다.
   1. ’(‘ 이전 괄호가 열린 괄호인 경우 -> 레이저 이므로 현재 스택 크기 -1 (하나는 레이저 괄호이므로) 을 answer 에 더해준다.
   2. ’)’ 이전 괄호가 닫힌 괄호인 경우 -> 막대기가 끝나는 지점이므로 answer 에 1을 더해준다. (막대기 갯수 하나가 더해지므로)
   3. 괄호 문제들처럼 닫힌 괄호가 나왔다는 건 괄호 하나가 끝났다는 의미이므로 스택의 탑(무조건 ‘(‘이다.)을 제거한다.
4. 마지막에 answer을 출력해준다.

문제 풀이

#pragma GCC optimize("Ofast")
#include <iostream>
#include <stack>
#include <string>
using namespace std;

stack<char> stk;
int answer = 0;
string str;

int main()
{
    ios::sync_with_stdio(0); cin.tie(0);

    cin >> str;
    for (int i = 0; i < str.length(); ++i)
    {
        if (str[i] == '(') stk.push(str[i]);
        else
        {
            if (str[i-1] == ')') answer++;
            else answer += stk.size() - 1;

            stk.pop();
        }
    }

    cout << answer << '\n';

    return 0;
}

다시 생각해 볼 점

1. 이렇게 입력 갯수가 안나와 있는 경우가 참 애매했다.
2. while(!cin.eof)로 받아보려고 했지만 로직은 맞는데 계속 틀리다고 나왔다.
3. 결국 string으로 전체 문자열을 다 받고, for문으로 순회했다.
4. 높은 등수를 받은 분의 코드를 보니

    char s[100'001];    // 아마 끝에 '\n'이 들어가야 해서 + 1 하신듯
    scanf("%s", s);     // 배열은 이름 = 시작시점의 주소 이므로 & 생략
    int len = strlen(s);    // 이 함수로 문자열의 길이를 구하는 듯
   

   이렇게 처리하신 것 같다.

5. 나도 앞으로 입력 갯수가 안주어지면 위와 같이 char배열과 strlen 함수로 구해야겠다.