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

문제 설명

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

10799번: 쇠막대기

 

접근 방법 - 스택을 이용한 수학적 사고력 문제

백준의 10799번 문제는 수학적 사고력이 필요한 스택 문제이다.

해당 문제는, 위 그림의 규칙을 기반으로 하여, 입력받은 괄호에 대한 총 쇠막대기의 개수를 구해야 하는 문제이다.

필자는 아래의 규칙을 찾았고, 이를 기반으로 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

필자가 괄호를 해석한 방식을 아래에 기재해놓으니 참고해보길 바란다.

 

필자가 발견한 규칙

문제에 게시된 그림에 필자가 몇 가지를 더 적어보았다. 참고해보길 바란다.

여기에서, ( ) 아래로 적어놓은 숫자는 ( )의 위치를 기점으로 하여 왼편에 있는 ( 개수와 동일한 것을 알 수 있다.

따라서 필자는 ( )를 만날 때마다 스택에 남아있는 ( 개수를 더하면서 정답을 구해보았다.

물론, 단순히 )를 만난 경우는 하나의 막대기의 끝부분임을 고려하며 코드를 작성하였다.

 

코드의 실행 순서

1) 스택을 선언하고, 괄호 문자열 전체를 입력받는다.

 

2) 정답을 저장할 sum 변수를 0으로 초기화하여 선언한다.

 

3) 문자열의 크기만큼 반복문을 수행하고, 아래의 연산을 수행한다.

- ( 를 만나면 스택에 push한다.

- ) 를 만나면 이전의 문자가 무엇인지 탐색한다.

연달아 (가 있었다면 해당 ( 문자에 대해 pop 연산을 취한 뒤, 현재 스택의 크기만큼 sum에 더한다.

아니라면, 이는 막대기가 끝난 지점임을 의미하기 때문에, (에 대해 pop 연산을 취한 뒤 sum에 1을 더한다.

 

4) 모든 연산이 끝났다면, 최종적으로 저장된 sum값을 출력한 뒤 실행 종료한다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#include <string>
#include <stack>
using namespace std;

//백준 10799번 코드
int main() {
	stack<char> s;
	string ch;
	cin >> ch;

	int sum = 0;
	for (int i = 0; i < ch.length(); i++) {
		if (ch[i] == '(') { s.push('('); }
		else {
			if (ch[i - 1] == '(') { s.pop(); sum += s.size(); }
			else { s.pop(); sum += 1; }
		}
	}

	cout << sum;
}

 

제출 결과

(2022.01.09 백준 10799번 문제 제출 결과)