cyphen156
백준-스택, 큐, 덱 1 4949 균형잡힌 세상 본문
문자열에 포함되는 괄호는 소괄호("()") 와 대괄호("[]")로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다.
- 모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다.
- 모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다.
- 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다.
- 모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다.
- 짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다.
앞서 푼 괄호의 응용문제
이 문제는 C와 C#으로 풀어놓은 것이 있어 이것도 같이 공유하겠다.
제약사항
- 온점이 들어오면 문자열은 끝난다.
- 0 < strlen <= 100
- 첫번째 문자 입력이 '.'이라면 루프 종료
주의 사항
" ."이 친구도 종료 시퀀스가 아닌 균형잡힌 문자열이다.CPP풀이
균형잡힌 세상_4949.cpp
/**
* 백준 균형잡힌 세상_4949
* 문자열에 포함되는 괄호는 소괄호("()") 와 대괄호("[]")로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다.
* 모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다.
* 모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다.
* 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다.
* 모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다.
* 짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다.
* 앞서 푼 괄호의 응용문제
* 이 문제는 C와 C#으로 풀어놓은 것이 있어 이것도 같이 공유하겠다.
*
* 제한사항
*****************************************
* 온점이 들어오면 문자열은 끝난다. *
* 0 < strlen <= 100 *
* 첫번째 문자 입력이 '.'이라면 루프 종료 *
*****************************************
*
*
*
* 주의
* " ."이 친구도 종료 시퀀스가 아닌 균형잡힌 문자열이다.
*
* 풀이시간 20분
*/
#include <iostream>
#include <string>
using namespace std;
static char stack[101];
static int top = -1;
void Push(char data);
char Pop();
bool IsEmpty();
int main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
while(1)
{
string str;
getline(cin, str);
top = -1;
// 종료 시퀀스
if (str.front() == '.')
{
break;
}
bool isVPS = true;
for (int i = 0; i < str.length(); ++i)
{
switch (str[i])
{
case '(':
Push('(');
break;
case '[':
Push('[');
break;
case ')':
{
char temp = Pop();
if (temp != '(')
{
isVPS = false;
goto ESCAPE;
}
break;
}
case ']':
{
char temp = Pop();
if (temp != '[')
{
isVPS = false;
goto ESCAPE;
}
break;
}
default:
break;
}
}
ESCAPE:
// 모두 비워지지 않았음
if (top != -1)
{
isVPS = false;
}
if (isVPS)
{
cout << "yes" << '\n';
}
else
{
cout << "no" << '\n';
}
}
return 0;
}
void Push(char data)
{
stack[++top] = data;
}
char Pop()
{
if (IsEmpty())
{
// 빈 스택에서 Pop 시도시 널문자 반환 ==> 특수조건으로 활용
return '\0';
}
return stack[top--];
}
bool IsEmpty()
{
if (top < 0)
{
return true;
}
return false;
}
균형잡힌 세상.C
/**
* 백준 균형잡힌세상 4949
*
* 문자열문제 괄호의 확장,
* 소괄호 : () 대괄호 []
*
*
* 제한사항
*****************************************
* 문자열의 입력 종료 시퀀스는 ~~'.' *
* 0 < str <= 100 *
* 프로그램 종료 시퀀스는 '.' *
*****************************************
*
* 유사 스택 사용
*
* 주의
* Help( I[m being held prisoner in a fortune cookie factory)].
* ()()[][]만 정상괄호 (보다 [의 길이가 길어서는 안됨
* 풀이시간 10분
*/
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
typedef struct Stack {
char ch[100];
int top;
int squareBrackets;
int parentheses;
}Stack;
void push(Stack* stack, char str) {
if (str == '(') {
stack->parentheses++;
}
else if (str == '[') {
stack->squareBrackets++;
}
stack->ch[stack->top] = str;
stack->top++;
}
int pop(Stack* stack, char str) {
if (str == ')') {
// 비정상 소괄호 입력
if (stack->parentheses <= 0
|| stack->ch[stack->top - 1] == '[') {
return -1;
}
stack->parentheses--;
}
else if (str == ']') {
//비정상 대괄호 입력
if (stack->squareBrackets <= 0
|| stack->ch[stack->top - 1] == '(') {
return -1;
}
stack->squareBrackets--;
}
stack->top--;
return 0;
}
int main() {
// 입력 길이 제한
char str[101];
Stack stack;
while (1) {
//스택 초기화
stack.parentheses = 0;
stack.squareBrackets = 0;
stack.top = 0;
int i = 0;
int err = 0;
for (; i < 100; ++i) {
str[i] = getchar();
if (str[i] == '.')
break;
if (str[i] == '(' || str[i] == '[') {
push(&stack, str[i]);
}
else if (str[i] == ')' || str[i] == ']') {
if (pop(&stack, str[i]) == -1) {
err = 1;
}
}
}
getchar();
if (i == 0)
break;
// 문자열 종료처리
str[i + 1] = '\0';
if (stack.top == 0 && stack.parentheses == 0 && stack.squareBrackets == 0 && err == 0) {
printf("yes\n");
}
else
printf("no\n");
}
return 0;
}
균형잡힌 세상.CS
// 4949 융택
// 균형잡힌 세상<
// 괄호 짝맞추기 문제
// 각 문자열은 마지막 글자(.)를 제외하고 영문 알파벳, 공백, 소괄호("( )"), 대괄호("[ ]")로 이루어져 있으며
// , 온점(".")으로 끝나고, 길이는 100글자보다 작거나 같다.
// --> 0 < Length <= 100호가 있다.
// ----> 열리는 괄호는 닫히는 괄호가 있다는
// 모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다.
// 모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다.
// --> if ([) --> Error
// 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다.
// --> 닫히는 괄호가 있다면 반드시 열리는 괄것을 반드시 보장하지는 못한다.
// 모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다.
// 짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다.
// --> 괄호 안에 괄호가 또 나올 수 있다.
// 스택 가져오기
class Stack
{
private int size;
private int[] datas;
public Stack(int initSize)
{
size = -1;
datas = new int[initSize];
}
~Stack() { }
public void Push(int inData)
{
if (size == datas.Length)
{
int newLength = datas.Length * 2;
int[] newDatas = new int[newLength];
for (int i = 0; i < datas.Length; i++)
{
newDatas[i] = datas[i];
}
datas = newDatas;
}
size++;
datas[size] = inData;
}
public int Pop()
{
if (IsEmpty())
{
return -1;
}
return datas[size--];
}
private bool IsEmpty()
{
if (size == -1)
{
return true;
}
return false;
}
public int Empty()
{
if (size == -1)
{
return 1;
}
return 0;
}
public int Size()
{
return size + 1;
}
public int Top()
{
if (IsEmpty())
{
return -1;
}
return datas[size];
}
public void Clear()
{
size = -1;
}
}
class Program
{
public static void Main()
{
StreamReader sr = new StreamReader(Console.OpenStandardInput());
StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());
// ( --> 1
// [ --> 2;
// MaxSize = 100
Stack stack = new Stack(100);
while (true)
{
stack.Clear();
string str = sr.ReadLine();
if (str == ".")
{
break;
}
char[] datas = str.ToCharArray();
bool isBalanced = true;
foreach (char ch in datas)
{
if (ch == '(')
{
stack.Push(1);
}
else if (ch == ')')
{
if (stack.Top() != 1)
{
isBalanced = false;
break;
}
else
{
stack.Pop();
}
}
else if (ch == '[')
{
stack.Push(2);
}
else if (ch == ']')
{
if (stack.Top() != 2)
{
isBalanced = false;
break;
}
else
{
stack.Pop();
}
}
}
// 스택이 비어있지 않음
if (stack.Empty() != 1)
{
isBalanced = false;
}
if (isBalanced)
{
sw.WriteLine("yes");
}
else
{
sw.WriteLine("no");
}
sw.Flush();
}
}
}
모든 예제 코드의 소스파일은 제 개인 깃허브 레포지토리에 있습니다.
Workspace/알고리듬 풀이 at main · cyphen156/Workspace
Studying . Contribute to cyphen156/Workspace development by creating an account on GitHub.
github.com
'컴퓨터공학 > 알고리듬 풀이' 카테고리의 다른 글
백준-스택, 큐, 덱 1 18258 큐 2 (1) | 2025.06.11 |
---|---|
백준-스택, 큐, 덱 1 12789 도키도키 간식드리미 (0) | 2025.06.11 |
백준-스택, 큐, 덱 1 9012 괄호 (0) | 2025.06.10 |
백준-스택, 큐, 덱 1 10773 제로 (0) | 2025.06.10 |
백준-스택, 큐, 덱 1 28278 스택 2 (0) | 2025.06.10 |