[BOJ/백준] 10799 쇠막대기

● [문제번호 10799] 쇠막대기

 

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

10799번: 쇠막대기

 

● 알아야 할 것

: stack 자료구조와 메소드

 

● 풀이 과정

: 풀이과정을 쉽게 떠올리기 어려웠다.

1. 레이저 기준 왼쪽 쇠막대기의 갯수는 stack.size() 이고 이를 결과값에 포함한다.

2. 그리고 연속해서 ')' 가 나오는 경우 그 갯수 만큼 결과값에 포함한다.

3. 1-2 를 문자열 길이동안 반복한다.

 

● 주의 할 것

: 쇠막대기 갯수 = stack.size( ) - 1 이다.

: 연속된 ')' 를 만났을 때 잘 생각해야 한다.

 

● 참고 할 것

: NULL

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

// '('는 쇠막대기의 시작이므로 알맞은 짝의 ')' 을 만나기 전까지 stack에 저장
stack<char> s;
// 문자열 저장을 위한 string
string str;
// 잘려진 쇠막대기 조각의 총 개수
int result;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> str;
    
    for(int i = 0; i < str.length(); i++)
    {
        // '(' 는 쇠막대기의 시작
        if(str[i] == '(')
        {
            s.push('(');
        }
        // 레이저의 시작
        else if(str[i] == ')')
        {
            // 레이저 기준 왼쪽 조각 (잘려진 쇠막대기) 을 결과값에 더하기
            result += s.size() - 1;
            
            // 연속된 ')' 가 있는 경우
            while(str[i] == ')')
            {
                // 추가로 있는 ')' 갯수 만큼 쇠막대기 낱개를 결과값에 더하기
                s.pop();
                i++;
                result++;
            }
            
            // 레이저의 시작인 ')' 빼기
            result--;
            
            // 반복문의 index값 조절
            i--;
        }
    }
    
    cout << result;
    
    return 0;
}

 

 

● [백준] - [알고리즘 기초 1/2] - [201 - 자료구조 1 (연습)] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	17413	단어 뒤집기 2	https://pirateturtle.tistory.com/165
2	10799	쇠막대기	https://pirateturtle.tistory.com/166
3	17298	오큰수	https://pirateturtle.tistory.com/167
4	17299	오등큰수	https://pirateturtle.tistory.com/168