[백준 BOJ][C++]10799번 쇠막대기 풀이: Stack

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

10799번: 쇠막대기

 

 10799번은 스택을 사용하여 문제를 해결할 수 있습니다. 

 

 스택(stack)은 FILO(First In Last Out) 형식의 자료구조로, 한 쪽 끝에서만 원소를 삽입(push), 삭제(pop)할 수 있습니다. 

 

 일반적으로 괄호 문제는 스택을 활용하여 푸는데요, 여는 괄호('(')는 스택에 push하고 닫는 괄호(')')를 만날때마다 스택의 원소를 하나씩 pop합니다. 

 

#include<iostream>
#include<cstring>
#include<stack>

using namespace std;


int main(void) {

	char str[100001];  //입력받을 문자열
	stack<char> s;  //스택
	int result = 0;  //결과
	int prev = 0;  //이전 닫는 괄호에서의 남은 막대기 수

	cin >> str;

	for (int i = 0; i < strlen(str); i++) {
		if (str[i] == '(') { //여는 괄호는 push
			s.push(str[i]);
		}
		else if (str[i] == ')') { 
			s.pop();  //닫는 괄호 만나면 여는 괄호 pop

			if (prev > s.size()) {  //막대기 끝
				result += 1; 
			}
			else {  //레이저
				result += s.size();  //s.size(): 남은 막대기 수 
			}

			prev = s.size();  //prev 값 reset
		}
	}

	cout << result << endl;

	return 0;
}

 

스택을 직접 구현할 수도 있지만 편의를 위해 C++ STL 스택 라이브러리를 이용하였습니다. 

 

•  변수 설명

• char str[100001];

 입력받은 문자열을 저장하는 배열

 

• stack<char> s;

 char 타입 원소를 갖는 스택, 여는 괄호('(') push & pop

 

• int result;

 쇠막대기의 총 조각 수 

 

• int prev;

 닫는 괄호(')')를 만났을 때, 이전 닫는 괄호에서의 남은 막대기 수

 

 

 

•  코드 설명

 for문을 통해 str에 저장된 문자들을 하나씩 탐색합니다.

 

 만약 str[i]가 여는 괄호('(')라면 스택(s)에 push 연산을 해줍니다. 

 

 만약 str[i]가 닫는 괄호(')')라면 스텍(s)에서 pop 연산을 해줍니다. 이때 스택의 크기(s.size())는 닫는 괄호를 만났을 때 아직 덜 잘린 남은 막대기 수를 의미합니다. 

 

 이전 닫는 괄호에서의 남은 막대기 수 prev 값보다 현재 남은 막대기 수 s.size()가 줄어들게 되면 가장 짧은 막대기의 끝 지점에 도달했음을 의미합니다. 이때, result 값을 갱신해야 하는데 남은 막대기 수가 아닌 가장 짧은 막대기의 마지막 조각을 더해주어야 함으로 result+=1;을 합니다.

 

 그렇지 않으면 레이저에 의해 잘린 조각 수 즉, 남은 막대기 수를 더해주어야 함으로 result+=s.size();을 합니다.