[알고리즘][스택] 9012번 괄호 | baekjoon 문제 풀이

 

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

9012번: 괄호

 

문제

간단한 스택 문제! 괄호의 짝을 찾으면 된다.

'('를 만나면 stack에 1을 넣고 ')'를 만나면 넣었던 1을 빼주면 된다.

 

풀이

#include <iostream>
#include <string>
#include <stack>
using namespace std;

bool isPS(string str) {
	int str_length = str.length();
	stack<bool> st;

	for (int i = 0; i < str_length; i++) {
		if (str[i] == '(') st.push(1);
		else {
			if (st.empty()) return false;
			else st.pop();
		}
	}
	if (st.empty()) return true;
	else return false;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int T = 0; 
	cin >> T;
	string s;

	for (int i = 0; i < T; i++) {
		cin >> s;
		if (isPS(s)) cout << "YES\n";
		else cout << "NO\n";
	}
}

 

 

 

과정

위의 제출 사진에서 볼 수 있듯이... 수행 시간에 차이가 있는데, 아래 코드의 유무 때문이었다.

ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

 

main에 적어주면 실행 속도가 빨라진다!까지는 기억을 하는데, 이유를 깜빡해서 다시 찾아봤다.

 

 

---

 

ios_base::sync_with_stdio(false);

>> C의 stdio와 C++의 iostream의 동기화를 '비활성화'로 전환한다.

 

[동기화 O]

- 평소에는 동기화가 되어있어, C와 C++이 동일한 버퍼를 공유한다. 

- 장점: 입출력에서 C와 C++ 스타일의 문법을 혼용하여 쓸 수 있다. 스레드(thread)로부터 안전하다.

- 단점: iostream과 stdio의 버퍼를 모두 사용하기 때문에 딜레이가 발생한다.

 

* 스레드에 대한 개념도 궁금해서 찾아보긴 했는데, 나중에 따로 글로 정리를 해야할 것 같다.

 

[동기화 X]

- 장점: C++ 표준 스트림이 독립적으로 IO 버퍼링을 하게 되어, 많은 양의 입출력이 있을 경우 성능이 많이 좋아진다.

- 알고리즘 문제 풀이에서는 예외 처리나 멀티스레드 작업이 필요하지 않기에 두 동기화를 끊고 성능을 높여 시간을 줄이는 게 더 효율적이다.

- 단점: 버퍼가 분리되었기 때문에 cin과 C의 scanf, gets, getchar 등을 같이 사용하면 안되고, cout와 C의 printf, puts, putchar 등과 같이 사용하면 안된다.

 

 

 

cin.tie(NULL); cout.tie(NULL);

>> 입력과 출력의 연결을 끊어준다 (평소에는 묶여있음)

 

- 장점: 내부적으로 cin과 cout을 묶어주는 과정을 수행하지 않기 때문에 시간이 절약됩니다.

- 단점: 입출력 순서를 보장받을 수 없다. 입력을 한 번에 받고, 출력이 나중에 한 번에 처리된다. 자연스럽지 못한 결과가 나올 수도 있다. but! 알고리즘 문제라면 크게 상관없으니까 쓰자!

 

 

 

https://velog.io/@gogori6565/BOJ-cin.tieNULL%EA%B3%BC-iosbasesyncwithstdiofalse

[BOJ/C++] cin.tie(NULL)과 ios_base::sync_with_stdio(false) 그리고 endl...

* 해당 블로그를 참고하여 내용을 정리하였다.