백준2800 괄호제거

작성일 | In

문제 링크

  • https://www.acmicpc.net/problem/2800

문제 출처

  • 2011/2012 COCI Contest #6 3번

사용 알고리즘

  • 스택
  • 비트마스크

시간복잡도

  • 문자열의 길이를 n, 괄호 쌍의 개수를 m이라 하면
    O(2mn)

풀이

  1. 가장 먼저 str이라는 문자열을 선언한 뒤, str을 입력받습니다.
  2. 괄호의 인덱스를 저장할 vector 를 하나 생성합니다.
  3. str을 순회하면서 ( 가 나오면 push하고, ) 가 나오면 pop을 한 뒤, ) 의 인덱스와 짝이 되는 (의 좌표를 저장합니다.
  4. bitmask 기법을 이용하여 괄호를 일정 부분 제거한 str을 각각 또 다른 vector에 저장합니다.
  5. 문자열을 오름차순으로 정렬합니다.
  6. 중복되지 않게 정렬된 결과를 출력합니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef pair<int, int> p;

string s;
vector<p> bra;
vector<string> ans;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> s;

	stack<int> stk;
	for(int i=0; i<s.size(); i++){
		if(s[i] == '(') stk.push(i);
		else if(s[i] == ')'){
			bra.emplace_back(stk.top(), i);
			stk.pop();
		}
	}

	int n = bra.size();
	int lim = 1 << n;
	for(int bit=1; bit<lim; bit++){
		string tmp = s;
		for(int i=0; i<n; i++){
			if(bit & (1<<i)) tmp[bra[i].x] = tmp[bra[i].y] = '.';
		}
		string now;
		for(auto i : tmp) if(i != '.') now += i;
		ans.push_back(now);
	}

	sort(ans.begin(), ans.end());
	cout << ans[0] << "\n";
	for(int i=1; i<ans.size(); i++){
		if(ans[i-1] != ans[i]) cout << ans[i] << "\n";
	}
}