[백준 알고리즘] 4949번 - 균형잡힌 세상 (런타임에러)

1. 문제, 실행결과 예시

 

 이번 문제의 알고리즘은 의외로 간단했다. 오히려 나를 괴롭힌것은 런타임에러와 문자열 처리 ㅠㅠ 문자열을 처리한다는 것이 얼마나 소중한지 알게되었다 ㅠㅠ 사실 오래전 부터 문자열을 처리하는 문제는 일단 겁을 먹었는데, 그 습관이 아직까지 온것 같다. 본론에서 다시 얘기할 것이고 문제를 먼저 보도록 하자.

 

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

4949번: 균형잡힌 세상

---

 

4949번

 

---

 다시 말하지만 알고리즘은 간단하다 저번문제(9012번)에서 대괄호와 중괄호를추가만 해주면 되기 때문이다. 나의발목을 잡은 것은 바로 문자열과 런타임 에러이다 ㅠㅠ 다음은 실행 예시이다.

 

---

 

결과 예시

 

---

 알고리즘은 저번 문제에서 전혀 다를게 없다. 중괄호와 대괄호를 검사해주는 기능만 추가하면 되기 때문이다. 아마 이번 페이지에서는 런타임 에러와 문자열 처리를 더 많이 다룰 것 같다.

 

2. 문제 풀이

 

 기본적인 알고리즘은 똑같다. 여는 괄호를 만나면 stack에 넣어주고 닫는 괄호를 만나면 pop하여 비교해주기만 하면 되기 때문이다. 그러나 문제는 바로 문자열의 입력이다. 공백도 입력 받아야 하며, 문자열 버퍼의 에러를 방지하기 위해 줄바꿈 문자를 입력받으면 안된다...... 다행이 이런 상황을 위한 해결책을 구글링을 통해 찾았다. 다음은 내가 작성한 입력 코드이다.

 

scanf("%[^\n]s", msg);
getchar();

 

 위의 문장에서 나오는 [] 사이의 문자는 'scan set' 이라고 한다. 이 기능에 대해서 더 자세히 다루고 싶지만 일단 문제를 푸는 과정에서 사용한 [^\n] 이 부분만 해석하자면, 줄바꿈 문자를 만나기 직전까지 읽어 드린다는 것이다. 그렇다면 버퍼에 남아있는 줄바꿈 문자는? 이 문자는 getchar() 를 사용해 먹어 치운다. 그렇게 되면 공백도 포함된 한줄의 문자를 읽어드릴 수 있다는 것이다. 사실 저 방식을 쓰기전에 사용한 방식이 있다. 바로 다음과 같은 코드이다.

 

for (int i = 0; i < 100; i++) {
	char input = getche();
	msg[i] = input;
	if (input == '.')
		break;
}

 

 이렇게 사용하면 입력 받을 때 마다 배열에 추가하고 종료조건인 '.' 문자가 입력될 때 입력을 마칠 수 있다. 그러나 런타임 에러...... 이유를 찾아 봤더니 getche() 함수를 포함한 헤더파일인 #include <conio.h> 헤더파일은 리눅스 상에서 지원이 되지 않고, 백준 알고리즘은 리눅스에서 채점을 하기 때문에 런타임 에러가 발생한 것이다! 혹시 이런 에러가 발생하신 분들은 참고하길 바란다!

 

- 배열 인덱스 참조에 의한 런타임 에러

 

 참고로 말하자면 나는 이번 문제를 해결하면서 엄청난 런타임 에러를 만났다 ㄷㄷ......

---

 

 

---

 일단 런타임 에러가 발생한 코드는 다음과 같다.

 

#define SIZE 100

class Stack {
private:

	char stack[101];
	int top;

public:

	Stack() { top = -1; }

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

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

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

#include <cstdio>

int main(void) {

	Stack stack;
	char msg[SIZE];

	while (1) {
		
		int state = 1;
		scanf("%s", msg);
	
		if (msg[0] == '.')
			break;

		for (int i = 0; msg[i] != '.' && i < SIZE; i++) {

			if (msg[i] == '{' || msg[i] == '(' || msg[i] == '[')
				stack.push(msg[i]);

			switch (msg[i]) {

			case '}':
				if (stack.pop() != '{')
					state = 0;
				break;
			case ')':
				if (stack.pop() != '(')
					state = 0;
				break;

			case ']':
				if (stack.pop() != '[')
					state = 0;
				break;
			default:
				continue;

			}
			if (state == 0)
				break;
		}

		if (state && stack.empty())
			printf("yes\n");
		else
			printf("no\n");
	}

	return 0;
}

 

 실제로 런타임 에러가 발생하는 이유는 여러가지가 있지만 내가 알고있는 대표적인 것은 바로 과하거나 적은 메모리 선언, 그리고 잘못된 배열의 참조이다. 그러나 메모리의 경우 최대로 입력받을 수 있는 수를 고료하여 스택과 문자열을 선언하였기 때문에 분명 다른곳에 문제가 있을 거라고 생각했다. 그래서 배열의 참조를 생각해봤다.

 

 for반복문의 중단문을 보면  (msg[i] != '.' && i < SIZE) 이렇게 되어있다.  논리곱의 연산자이기 때문에 별 문제가 없어보이지만 바로 이부분 때문에 런타임 에러가 난 것이다. 논리 연산자는 왼쪽에서 오른쪽으로 진행된다. 즉 i가 SIZE보다 작은지를 검사하기 전에 msg[i] 가 '.'이 아닌지를 먼저 검사한다는 것이다. 그렇게 된다면 문제가 발생한다. 바로 i가 100일때도 msg[i]가 '.'이 아닌지를 검사하게 되고 바로 여기서 런타임 에러가 발생한다는 것이다! 그래서 생각한 방법은 바로 이둘의 위치를 바꾼 것이다.

 

 즉, (msg[i] != '.' && i < SIZE) 대신 (i < SIZE && msg[i] != '.') 를 사용하면 되는 것이다. 이유는 간단하다. 논리곱 연산자의 경우 왼쪽의 결과가 거짓이면 오른쪽의 식은 실행하지 않는다. 즉 i가 SIZE의 값과 같거나 크다면 msg[i] != '.'의 식은 실행하지 않기 때문에 결과적으로는 런타임 에러를 피할 수 있다.

 

 다음은 최종적인 코드이다.

 

#define SIZE 100

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 empty() {
		return top == -1 ? 1 : 0;
	}

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

#include <cstdio>

int main(void) {

	Stack stack;
	char msg[SIZE];

	while (1) {
		
		int state = 1;
		stack.reset();

		scanf("%[^\n]s", msg);
		getchar();
	
		if (msg[0] == '.')
			break;

		for (int i = 0;  i < 100 && msg[i] != '.'; i++) {

			if (msg[i] == '{' || msg[i] == '(' || msg[i] == '[')
				stack.push(msg[i]);

			switch (msg[i]) {

			case '}':
				if (stack.pop() != '{')
					state = 0;
				break;
			case ')':
				if (stack.pop() != '(')
					state = 0;
				break;

			case ']':
				if (stack.pop() != '[')
					state = 0;
				break;
			default:
				continue;

			}
			if (state == 0)
				break;
		}

		if (state && stack.empty())
			printf("yes\n");
		else
			printf("no\n");
	}

	return 0;
}

 

3. 결어

 

 비록 런타임 에러 때문에 힘든 일을 겪었지만...... 다행이도 잘 해결되었다. 사실 이렇게 모르는 것을 해결하기 위해 알고리즘 문제를 푸는 것이기 때문에 오히려 이렇게 여러 문제를 만났다는 것이 더 다행이라고 생각한다. 지금 나에게 부족한것은 (한가지가 아니지만) 문자열 처리와 버퍼에 대한 지식이 부족하다는 것이다. 이 부분에 대해 이 블로그를 통해 정리했으면 좋겠다.