[백준(BOJ)] 10799번 쇠막대기 C++

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

10799번: 쇠막대기

어떤 문제인가?

문제에 특별한 어려움은 없는 문제였다. 

레이저를 기준으로 잘린 쇠막대기의 개수를 구하면 된다.

 

접근 방법

문제를 읽고 고민 없이 바로 stack을 사용하기로 결정했다.

입력받은 문자열의 index를 하나하나 살펴보면서 각각에 경우에 따른 처리를 해주면 된다.

 

int cnt = 0;
stack<char> stick;

잘린 쇠막대기의 개수를 셀 cnt를 0으로 초기화해준다.

괄호를 넣어둘 char stack을 선언해준다.

 

string s;
cin >> s;

문자열을 입력받는다.

 

for (int i = 0; i < s.length(); i++) 

이제 for문을 순회하며 문자열을 하나하나 살펴보도록 하자.

 

 

if (s[i] == '(') {
    stick.push(s[i]);
} 

먼저 '(' 인경우이다. 

이 경우는 쇠막대기가 시작되는 부분이므로 stack에 추가해준다.

 

 

else if (s[i] == ')' && s[i - 1] == '(') {
    stick.pop();
    cnt += stick.size();
} 

그다음 경우로 레이저가 나오면 stack을 한번 pop 해준다.

왜냐하면 첫 번째 경우에서 레이저인지 쇠막대기의 시작 부분인지 상관없이 stack에 추가해줬다.

하지만, 여기서  이전에 추가된 '('가 쇠막대기의 시작 부분이 아니라 레이저임을 알 았으니 삭제해주는 것이다.

 

그리고 stack의 크기만큼 cnt에 더해준다. 

왜냐하면 이 레이저를 기준으로 쇠막대기의 개수만큼 잘리기 때문이다. 

 

 

 

else if (s[i] == ')') {
    stick.pop();
    cnt++;
}

마지막으로 쇠막대기의 끝 부분인 경우이다. 

이 경우에는 한 개의 쇠막대기가 끝이 났으므로 stack을 pop 해주어 크기를 감소시킨다.

그리고 cnt를 1 증가시킨다.

 

cout << cnt;

모든 문자열을 탐색한 후 cnt를 출력해주면 끝!!

 

 

무엇이 어려웠는가?

stack을 사용해야 한다는 것을 떠올리기만 했다면 문제를 푸는 데는 큰 어려움이 없을 것 같은 문제였다.

문제를 읽으며 코드를 짜기 시작한다면 쉽게 풀릴 구현 문제이다.

 

시간 복잡도

입력한 문자열의 크기 n만큼 문자열의 index를 탐색하고 문자에 맞는 연산을 해야 한다.

따라서 시간 복잡도는 O(n)이다.

 

https://github.com/farmJun/Algorithm_BOJ_PS/blob/main/%EC%8D%B8%EB%A8%B8%EC%BD%94%EB%94%A9/10799.cpp

GitHub - farmJun/Algorithm_BOJ_PS: 백준 알고리즘 문제풀이 기록 레포짓입니다.