acmicpc.net / 알고리즘 기초 1/2 - No.10799 - 쇠막대기

알고리즘 기초 1/2 - No.10799 - 쇠막대기

 

TODO

- 쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있습니다.

- 쇠막대기를 다른 쇠막대기 위에 놓는 경우 완전히 포함되도록 놓되, 끝점은 겹치지 않도록 놓습니다.

- 각 쇠막대기를 자르는 레이저는 적어도 하나 존재합니다.

- 레이저는 어떤 쇠막대기의 양 끝점과도 겹치지 않습니다.

 

Constraints

0 ≦ S ≦ 100,000

 

Sample Input

()(((()())(())()))(())

(((()(()()))(())()))(()())

 

Sample Output

17

24

 

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

using namespace std;


int main() {
    vector<int> pieces;

    string str;
    cin>>str;

    int answer=0;

    for(int i=0; i<str.size(); i++) {
        if(str[i]=='(') {
            pieces.push_back(str[i]);
        } else {
            pieces.pop_back();
            if(str[i-1]=='(') {
                answer += pieces.size();
            } else { 
                answer++;
            }
        }
    }
    cout<<answer<<"\n";
}

How I tried this :

사실 괄호 갯수 2개일때 해결 하는 함수 재귀함수 생각도 해보고

index 층을 쌓아서 층마다 적용되는 (막대기마다) 레이져 갯수 찾아서 나누기 등등 

다양하게 고민했지만 너무나 복잡해서 해결해내지 못했다..

살짝 팁을 얻으려고 검색해본 첫 블로그가 ')' 만났을때 레이져면 막대기 갯수/ 막대기 끝나는거면 +1개  알려줫는데.. 너무나 쉽게 풀려버림...

이틀간 계속 도전하다 허탈..

 

정답을 아는거보다 1000줄로라도 풀었어야 맞는건지. 풀고 허탈감에 빠지는게 맞는건지...

 

프로그래머스로 접하고 복붙할뿐인데 잘풀렸다. 특별한건 없지만

 

What I got is : 

Main.cc: In function ‘int main()’:
Main.cc:16:19: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::__cxx11::basic_string<char>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
     for(int i=0; i<str.size(); i++) {
                  ~^~~~~~~~~~~

경고 뜬 채로 맞긴했지만 찝찝함.. 

 

I have to study :

 

경고 해결해보기