Notice
Recent Posts
Recent Comments
«   2025/07   »
1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30 31
Today
Total
Archives
관리 메뉴

cyphen156

백준-스택, 큐, 덱 1 4949 균형잡힌 세상 본문

컴퓨터공학/알고리듬 풀이

백준-스택, 큐, 덱 1 4949 균형잡힌 세상

cyphen156 2025. 6. 10. 12:48

균형잡힌 세상

문자열에 포함되는 괄호는 소괄호("()") 와 대괄호("[]")로 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