[C언어 / 백준 - 15926] 괄화왕 (스택 풀이법)

www.acmicpc.net/problem/15926

15926번: 현욱은 괄호왕이야!!

문제

여는 괄호 ‘(’와 닫는 괄호 ‘)’로 구성된 문자열에서 아래의 조건을 만족하는 문자열을 올바른 괄호 문자열이라고 부른다.

1. () 는 올바른 괄호 문자열이다
2. 어떤 문자열 x가 올바른 괄호 문자열이라면, (x)도 올바른 괄호 문자열이다.
3. 어떤 문자열 x와 y가 올바른 괄호 문자열이라면, xy도 올바른 괄호 문자열이다.

현욱은 친구로부터 생일 선물로 굉장히 긴 괄호 문자열을 받았다(도대체 왜 이런 걸 선물하는걸까?). 하지만 현욱은 올바른 괄호 문자열이 아니면 굉장히 싫어하기 때문에, 받은 괄호 문자열에서 연속한 일부분을 잘라서 올바른 괄호 문자열을 만들려고 한다. 그리고 이왕이면 긴 문자열이 좋으니 현욱은 부분 구간을 최대한 길게 잘라내려고 한다. 현욱을 도와 주어진 괄호 문자열에서 위의 조건을 만족하는 가장 긴 부분 문자열의 길이를 계산하는 프로그램을 작성해보자.

입력

첫 줄에 문자열의 길이 n (1 ≤ n ≤ 200,000)이 주어진다.

둘째 줄에 괄호로만 구성된 길이 n짜리 문자열이 주어진다.

출력

주어진 문자열에서 길이가 가장 길면서 올바른 괄호 문자열인 부분 문자열의 길이를 출력한다. 올바른 괄호 문자열인 부분 문자열을 찾을 수 없는 경우 0을 출력한다.

예제 입력 1 복사

5

(())(

예제 출력 1 복사

4

 

 

괄호문제는 언제나 그렇듯 스택을 사용하는 문제이지만 이 문제는 내 실력도 부족하지만 오랜만에 스택을 풀어서 한참을 헤매다 동기 형한테 물어보고 도움을 받아 푼 문제이다. 그 풀이를 기록해두려한당

 

이 문제에서 고려해야할 부분은

1) '(' 가 처음 시작하는 괄호인지 / 연속된 괄호에서의 시작인지

2) ')' 가 모든 괄호를 끝내는 괄호인지 / 연속된 괄호 중 안의 괄호를 끝내는 괄호인지

3) 연속되는 괄호의 연결을 끊는 불필요한 괄호인지를 확인할 수 있는지

정도..?가 될 것 같다.

 

이것을 전부 고려하여 사용한 방법을 예로 들면

( ( ) ) ( 가 있을 때 올바른 괄호는 (())가 되고 불필요한 괄호는 (가 된다. 그리고 괄호의 각각 범위를 배열에 저장해주는 것이다. 범위로 사용할 배열을 모두 -1로 저장해준 후 범위가 지정된 부분은 그 범위에 해당하는 index를 넣어주고 불필요한 괄호인 경우에는 0을 넘어줌으로써 구분해준다. 범위의 value를 넣을 때에는 여는 괄호에만 값을 넣어주고 닫는 괄호는 그대로 -1을 넣어주어 불필요한 연산은 하지 않도록 해준다(어처피 같은 범위이므로)

(	(	)	)	)
idx -> 3	idx->2	-1	-1	0

이렇게 배열을 초기화 해주면 -1인 값을 가지고 있는 곳은 고려해줄 필요가 없고

0과 0이 아닌 value를 가진 곳만 고려해주면 된다.  0이 아닌 곳을 고려할 때에는 여는 괄호 위치에 닫는 괄호index값이 들어있기 때문에 그 길이만큼 건너뛰어주고 저장되어있는 닫는 괄호 다음으로 넘어가주어 다음 값을 확인해준다. 

다음 값이 또 0과 -1이 아닌 값이라면 연속된 괄호라는 뜻인걸 고려하여 더해준다, (이 과정 반복)

0인 값이 사이에 있을 경우에는 연속된 괄호가 불가능하다는 것이기 때문에

0이 존재하지 않을 경우에는 계속해서 값을 더해주어 최신화해주고 0이 오게 될 경우 지금까지의 최대값과 비교하여 더 큰 값을 저장하도록 하는 것이다,

 

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>
#define MAX_SIZE 200003
#define MAX(a,b) a<b?b:a

typedef struct Intstack {
	int size;
	char stack[MAX_SIZE];
}Intstack;

typedef struct stack {
	int size;
	int stk[MAX_SIZE];
}stack;

stack ps;
Intstack s;
char str[MAX_SIZE];
int visited[MAX_SIZE];
int N,len,res;

void Init_stack(Intstack* s,stack *ps) {
	s->size = 0;
	ps->size = 0;
}

int Push(Intstack* s, char x) {
	if (s->size + 1 > MAX_SIZE) return 0;
	s->stack[s->size++] = x;	
	return 1;
}

int Push_s(stack* ps, int x) {
	if (ps->size + 1 > MAX_SIZE) return 0;
	ps->stk[ps->size++] = x;
	return 1;
}

char Pop(Intstack* s) {
	if (s->size <= 0) return 0;
	else return s->stack[--s->size];
}

int Pop_s(stack* ps) {
	if (ps->size <= 0) return 0;
	else return ps->stk[--ps->size];
}


char top(Intstack* s) {
	if (s->size <= 0) return 0;
	else return s->stack[s->size - 1];
}

int top_s(stack* ps) {
	if (ps->size <= 0) return 0;
	else return ps->stk[ps->size - 1];
}

int Size(Intstack* s) {
	return s->size;
}

int Size_s(stack* ps) {
	return ps->size;
}

void Input() {
	scanf("%d", &N);
	scanf("%s", str);
	memset(visited, -1, sizeof(visited));
}
// 반례 6 - ()(()(

void Solve() {
	for (int i = 0; i < N; i++) {
		if (str[i] == '(') {
			Push(&s, str[i]);
			Push_s(&ps, i);
		}
		else {
			if (top(&s) == '(') {
				Pop(&s);
				visited[Pop_s(&ps)] = i;
			}
			else {
				Push(&s, str[i]);
				visited[i] = false;
			}
		}
	}
	while (Size_s(&ps)) {
		visited[Pop_s(&ps)] = false;
	}
}

void func() {
	int k = 0;
	while (1) {
		if (k >= N) break;

		if (visited[k] == -1) {
			k++;
		}
		else if (visited[k] == 0) {
			Push_s(&ps, visited[k]);
			k++;
		}
		else {
			Push_s(&ps, (visited[k]-k+1));
			k += (visited[k]-k + 1);
		}
	}
	
	while (Size_s(&ps)) {
		int x=Pop_s(&ps);
		if(x!=0){
			len+=x;
		}
		else{
			res=MAX(len,res);
			len=0;
		}
	}
	res = MAX(len, res);
}

int main() {
	Input();
	Solve();
	func();
	printf("%d", res);

	return 0;
}

 

이 문제를 풀면서 나는 항상 매번 다른 식으로 문제를 풀고 있다고 느꼈다.

같은 자료구조를 쓰게 되면 어떻게 사용해서 어떻게 풀어야지 떠올라야하는데

같은 자료구조를 쓰더라도 매번 다르게 풀어 짧은 시간에 해결 할 수 있는 문제도 시간과 문제분석이 오래걸린다는 단점이 존재했다.

 

블로그 기록을 통해 이러한 문제점들을 보완하고자 한다