[백준] 4949. 균형잡힌 세상

: solved.ac class 2 - silver 4

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

4949번: 균형잡힌 세상

 

+ 힌트 : 7번째의 " ."와 같이 괄호가 하나도 없는 경우도 균형잡힌 문자열로 간주할 수 있다.

 

 

예제 입력

So when I die (the [first] I will see in (heaven) is a score list).
[ first in ] ( first out ).
Half Moon tonight (At least it is better than no Moon at all].
A rope may form )( a trail in a maze.
Help( I[m being held prisoner in a fortune cookie factory)].
([ (([( [ ] ) ( ) (( ))] )) ]).
 .
.

 

예제 출력

yes
yes
no
no
no
yes
yes

 

정답

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#define SIZE 101


int main() {

	char stnc[SIZE], stack[SIZE];

	while (1) {
		gets(stnc);
		if (stnc[0] == '.') break;

		int top = -1;

		for (int i = 0; stnc[i] != '.'; i++) {

			if (stnc[i] == '(' || stnc[i] == '[')
				stack[++top] = stnc[i];

			else if (stnc[i] == ')')
				if (top > -1 && stack[top] == '(') --top;
				else {top = -2; break;}

			else if (stnc[i] == ']')
				if (top > -1 && stack[top] == '[') --top;
				else { top = -2; break; }
		}

		puts(top == -1 ? "yes" : "no");
	}

	return 0;
}

---

해설

 

• 스택을 이용한다.
• -> 여는괄호 (, [ 가 들어오면 스택에 push하여 담고, 그에 상응하는 닫는괄호 ), ] 와 만나면 pop되게 한다.
• -> 괄호들이 짝을 맞추어 만나지 못한 경우 ex) ( [ ) ] 스택 안에는 괄호들이 그대로 남아 있을 것이다.
• -> 반복문을 통해 문장이 끝날 때까지 위 절차를 반복한다.
• -> 문장이 끝나면 스택의 top을 검사한다.
• 괄호들이 올바른 짝을 만나 pop되었다면 스택이 비어 top은 초기값으로 돌아와 있을 것이고, 아니라면 다른 값이 되어 있을 것이다. 전자의 경우 yes, 후자의 경우 no를 출력한다.

+ 여는괄호 없이 닫는괄호가 먼저 입력된 경우 반복문을 중단하고 무조건 no를 출력하도록 한다.

 

 

 

1. 배열의 최대 크기를 매크로 상수로 선언해 준다. 문자열 최대 길이인 100글자에 널 문자를 더한 101이다.

문자열을 넣어줄 stnc 배열과 스택으로 사용할 배열을 각각 최대 크기로 선언한다.

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#define SIZE 101


int main() {

	char stnc[SIZE], stack[SIZE];
	//입력받은 문자열을 넣어줄 배열과 스택으로 사용할 배열

 

2. 문자열을 하나씩 입력받는다. 스택의 top도 미리 -1로 초기화시켜 둔다.

	while (1) {
		gets(stnc); //문자열 입력
		if (stnc[0] == '.') break; // 입력의 끝 인식

		int top = -1; //스택의 top

+ 의외로 이 부분에서 상당히 헤맸다. " ." (공백이 하나 들어오고 온점이 들어오는 경우) 와 "."(온점만 들어오는 경우)를 잘 구분해야 한다.

전자는 '문자열 입력'으로, 후자는 '입력의 종료 신호'로 간주한다.

따라서 배열의 첫 인덱스에 '.'이 들어온 경우는 break; 문을 통해 반복문을 종료시켜 주어야 한다.

 

 

3. 자세한 설명은 주석으로 대체한다.

		for (int i = 0; stnc[i] != '.'; i++) {

			//여는 괄호를 입력받으면 스택에 push()
			//스택의 top은 1 증가하고, 스택에 괄호가 입력됨
			if (stnc[i] == '(' || stnc[i] == '[')
				stack[++top] = stnc[i];

			//닫는 괄호가 입력된 경우(소괄호)
			else if (stnc[i] == ')')

				//스택이 비어 있지 않으며,
				//짝이 되는 괄호가 스택에 존재한다면 pop()
				if (top > -1 && stack[top] == '(') --top;

				//아닌 경우 틀린 문장으로 간주하고
				//곧바로 while문 탈출
				else {top = -2; break;}

			//대괄호의 경우에도 위와 같게 처리
			else if (stnc[i] == ']')
				if (top > -1 && stack[top] == '[') --top;
				else { top = -2; break; }
		}

 

 

4. 위 for문으로 문장을 하나 검사할 때마다 결과값을 출력해 준다. 

		//스택이 비어 있다면 (top이 -1이라면) yes
		//맞지 않는 괄호가 입력되었거나 짝이 없어 스택이 차 있다면 no
		puts(top == -1 ? "yes" : "no");
	}

	return 0;
}