[백준 알고리즘] 9012번 - 괄호 검사 코드

1. 문제, 실행결과 예시

 

 이번 문제는 stack()의 활용 문제이다. 이전 문제(10773번)는 기본적인 스택의 기능을 확인해보는 문제라면, 이번 문제는 스택을 가지고 어떻게 활용할 수 있는지에 대한 문제 같다. (적어도 나의 지식 한에서)

 

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

9012번: 괄호

---

백준 알고리즘 9012번

---

 다행이도 소괄호만 해당하는 괄호 문자열을 다루는 문제였다 ㅎㅎ 사실 전에 중괄호와 대괄호까지 다뤄보는 문제를 마주친 적이 있었는데, 풀었던 기억을 까먹어서 ㅠㅠ 새로 시작하는 기분이었다. 다음은 실행결과 예시이다.

 

---

실행결과 예시

---

 자 문제를 정리하자면 소괄호만으로 이루어진 문자열이 주어지고, 이 괄호들이 잘 닫혔는지를 판별하는 문제인 것 같다.

사실 문제의 설명에 집합, 새로운 문자열과 같이 방법의 힌트 같은 단어들이 많이 주저이지만, 햇갈리지말자! 결국 우리가 풀어야할 문제는 주어진 소괄호들이 잘 닫혔는지만을 판별하는 것이다.

 

 그럼 어떤 방법으로 해야할까? 힌트아닌 힌트였지만 (사실 엄청난 힌트였다 ㅎㅎ) 이 문제는 문제 분류가 '스택' 이었으며, 스택을 사용해야 한다는 사실을 우리는 알 수 있다. 다음은 스택을 사용하여 문제를 푸는 과정이다.

 

2. 문제 풀이

 

 잘 닫힌 괄호의 구조를 생각한다면 하나의 답을 찾을 수 있다. 닫힌 괄호를 만난다면 가장 가까운 괄호가 열린 괄호이어야 하고 이렇게 짝이 맞은 괄호는 계산에서 제외하면 된다. 이 방식대로 진행하면 문제를 풀 수 있다. 다음은 위의 방법에 대한 예이다.

 

---

만약, (    )    (    )    (    (    (    )    (    )    )    ) 이런 문자열이 있다고 가정해보자, 왼쪽에서 오른쪽으로 진행되는 방향에서 닫는 괄호를 만난다면 왼쪽을 기준으로 가장 가까운 열린 괄호를 제외하고 계산을 진행면된다. 이 방법을 그대로 적용해보겠다.

 

(    )    (    )    (    (    (    )    (    )    )    )

위의 문자열에서 가장 먼저 만나는 닫힌괄호를 빨간색으로 표시하였고 왼쪽에서 가장 가까운 열린 괄호를 파란색으로 표시하였다. 이 둘을 제외하면 다음과 같은 문자열이 된다.

 

(    )    (    (    (    )    (    )    )    )

같은 방식으로 한번 더 진행하면 다음과 같은 문자열이 된다.

 

(    (    (    )    (    )    )    )

 

자, 그럼 햇갈리는 부분이 온다. 하지만 원리대로만 진행하면 충분히 가능한 문제이다. 가장 먼저 만나는 '닫는 괄호'를 빨간색으로 표시하고, 그 닫는 괄호를 기준으로 왼쪽에서 가장 먼저 만나는 '여는 괄호'에는 파란색을 표시해보자, 만약 위의 문장을 정확하게 이해 했다면 다음과 같은 그림이 나올것이다.

 

(    (    (    )    (    )    )    )

위의 괄호쌍을 제외하면 아래와 같은 문자열이 될것이다.

 

(    (    (    )    )    )

자 그럼 다시 차례로 진행해보자.

 

(    (    (    )    )    )

 

(    (    )    )

 

(    (    )    )

 

(    )

 

(    )

 

빈 문자열

---

 

자 하나의 반복대로 괄호 문자열이 사라질 때 까지 반복하였고, 원하는 결과를 얻었다. 이것은 곧 충분히 코드로 작성할 수 있다는 것을 의미한다. 다음은 코드를 구현하는 과정이다.

 

-stack 클래스 구현

 

이번 stack 클래스는 전에 구현했던 스택과는 다르게, 스택을 초기화해주는 reset() 메소드를 구현하였다. 이유는 조금 뒤에서 설명할 것이다.

 

#define SIZE 50

class Stack {
private:

	char stack[SIZE];
	int top;

public:

	Stack() { top = -1; }

	void push(int x) {
		stack[++top] = x;
	}

	int pop() {
		return top == -1 ? -1 : stack[top--];
	}

	int size() {
		return top + 1;
	}

	int empty() {
		return top == -1 ? 1 : 0;
	}

	void reset() {
		top = -1;
	}
};

 

-main() 함수

 

 위의 방법에서 stack을 활용하면 매우 편해진다. 원리는 다음과 같다.

 

• 입력받는 문자열 만큼 반복한다.
• 여는 괄호를 만나면 stack에 push한다.
• 닫는 괄호를 만나면 stack에서 pop한 값이 여는 괄호면 넘어가고 여는 괄호가 아닌 값이라면, 이 문자열은 잘못된 문자열이므로, 코드를 중단하고 NO를 출력한다.
• 마지막까지 반복했을 때, stack에 값이 남아있지 않으면 YES를 출력하고, 값이 남아 있다면 NO를 출력한다

다음은 위의 알고리즘을 구현한 코드이다.

 

#include <cstdio>
#include <cstring>
#include <cstdlib>

int main(void) {

	Stack stack;
	char *pMessage = (char*)malloc(sizeof(char) * 50);
	int num;
	scanf("%d", &num);
	getchar();
	
	for (int i = 0; i < num; i++) {
		int ans = 1;
		scanf("%s", pMessage);
		getchar();

		while (*pMessage) {
			
			if (*pMessage == ')') {
				if (stack.pop() != '(') {
					ans = 0;
					break;
				}
				else
					pMessage++;
			}
			else
				stack.push(*pMessage++);
		}

		if (ans && stack.empty())
			printf("YES\n");
		else
			printf("NO\n");
	}
	return 0;
}

 

 아쉽게도 위의 코드를 그대로 실행하면, 오류가 난다. (나도 엄청 해맸다 ㅠㅠ) 이유는 앞에서 계산한 문자열의 값이 stack에 남아있는 경우, 그 stack그대로 계산을 진행하기 때문에 오류가 발생하는 것이다. 그리고 이것이 바로 reset메소드가 있는 이유이다. 입력받기전 한번씩 스택을 초기화한다면 stak에 남아있는 값들은 신경쓰지 않아도 되기 때문이다. 다음은 수정한 코드이다. (수정이랄것도 없다. 그저 코드를 한 줄 추가했을 뿐이다 ㅎㅎ)

 

int main(void) {

	Stack stack;
	char *pMessage = (char*)malloc(sizeof(char) * 50);
	int num;
	scanf("%d", &num);
	getchar();
	
	for (int i = 0; i < num; i++) {
		int ans = 1;
		scanf("%s", pMessage);
		getchar();

		while (*pMessage) {
			
			if (*pMessage == ')') {
				if (stack.pop() != '(') {
					ans = 0;
					break;
				}
				else
					pMessage++;
			}
			else
				stack.push(*pMessage++);
		}

		if (ans && stack.empty())
			printf("YES\n");
		else
			printf("NO\n");

		stack.reset();
	}
	return 0;
}

 

3. 결어

 

오늘 백준 알고리즘에 순위가 있다는 것을 처음 알았다...... 확인해보니 나는 아직 아무것도 아니라는 것을 알 수 있었다...... (대체 7천 문제는 어떻게 푼거지......) 정말 분야에서 빛나는 사람은 하루에 한개가 아닌 수십개의 문제를 푸는 것 같기도 하다......

 내 자신의 위치를 아는것은 정말 어렵고 또 무서운 일이다. 객관적인 판단이 가능한지도 모르겠고 설사 객관적인 판단으로 확인해본 나의 위치가 형편없을 수도 있다. 블로그에 글을 올렸다고 만족한 내가 부끄러웠다. 목표는 500위 안이다. 백준 알고리즘 사이트에서 500위 안에 들것이다. 목표는 1년 안이지만...... 그게 가능할지 모르겠다...... 하지만 이렇게 목표라도 세워야 마음이 편할 것 같다.