[Python/Java] 백준 4949번. 균형잡힌 세상

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

4949번: 균형잡힌 세상

문제 설명:

 

받은 문자열이 균형이 맞는지 판단하는 문제이다.

• 모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다.
• 모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다.
• 짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다.

문제를 보았을때 괄호문제와 별 다를점이 없다.

 

풀이 설계

• flag 를 설정한다. 디폴트는 True
• 입력받을때 온점이 찍히면 문자열 받는걸 끝내야 한다. -> 받은 문자열의 가장 마지막이 온점인지 검사
• 온점이면 다른문자열을 받기위해(다시 입력을 받기 위해) 입력은 break한다.
• "(" 이거나 "[" 이면 스택에 담는다.
• ")" 이거나 "]" 이면 짝이 맞는지 확인이 필요하다. 이때 비교를 해야함으로 스택은 비어있으면 안된다.
  • 스택의 마지막과 받은 문자의 짝이 맞으면 pop을 해도 된다.
  • 아니라면 굳이 더이상 필요가 없기때문에 break 한다. (균형잡힌게 아닌 것)
• ")" 이거나 "]" 을 받은 문자인데 스택이 비어있으면 비교 할 대상이 없다. ( 짝이 없어서 균형잡힌게 아님 )
  • flag 을 바꿔준다.
• 비교가 끝나고 스택에 아무것도 없다면 괄호가 모두 짝을 찾아 남은게 없는 것 yes 출력

Python

# ")" 이거나 "]" 이면 짝 확인을 위한 dict
dic = {
    ")":"(",
    "]":"["
}

# 입력받을때 온점이 찍히면 문자열 받는걸 끝내야 한다. 
def input_check():
    data = input()
	# -> 받은 문자열의 가장 마지막이 온점인지 검사
    if data.endswith("."):
        return data

while True:
    data = input_check()
    # 온점이면 다른문자열을 받기위해(다시 입력을 받기 위해) 입력은 break한다.
    if data == '.':
        break
    stack = []
    flag = True
    for val in data:
    	# "(" 이거나 "[" 이면 스택에 담는다.
        if val == "(" or val == "[":
            stack.append(val)
        # ")" 이거나 "]" 이면 짝이 맞는지 확인이 필요하다. 이때 비교를 해야함으로 스택은 비어있으면 안된다.
        elif (val == ")" or val == "]") and stack:
        	# 스택의 마지막과 받은 문자의 짝이 맞으면 pop을 해도 된다.
            if stack[-1] == dic[val]:
                stack.pop()
            # 아니라면 굳이 더이상 필요가 없기때문에 break 한다. (균형잡힌게 아닌 것)
            else:
                break
        # ")" 이거나 "]" 을 받은 문자인데 스택이 비어있으면 비교 할 대상이 없다. ( 짝이 없어서 균형잡힌게 아님 )
        elif val == ")" or val == "]"and len(stack) == 0:
            flag = False
            break

    if flag == False or stack:
        print("no")
    # 비교가 끝나고 스택에 아무것도 없다면 괄호가 모두 짝을 찾아 남은게 없는 것 yes 출력
    else:
        print("yes")

 

 

Java

import java.util.*;

public class Baekjoon_4949 {
    public static String inputDataCheck(){
        Scanner inner = new Scanner(System.in);
        String data = inner.nextLine();
        if(data.endsWith(".")){
            return data;
        }
        return null;
    }
    public static void main(String[] args) {
        Map<String, String> dic = new HashMap<>();
        dic.put(")", "(");
        dic.put("]", "[");

        while(true){
            String sentence = inputDataCheck();
            if (sentence.equals(".")){
                break;
            }

            Stack stack = new Stack();
            Boolean flag = true;
            for (String alpha: sentence.split("")) {
                if (alpha.equals("(") || alpha.equals("[")){
                    stack.push(alpha);
                } else if (alpha.equals(")") || alpha.equals("]")) {
                    if (stack.isEmpty()){
                        flag = false;
                        break;
                    }
                    if (stack != null && dic.get(alpha).equals(stack.peek())){
                        stack.pop();
                    }else{
                        flag = false;
                        break;
                    }
                }
            }

            if (flag == false || !stack.isEmpty()){
                System.out.println("no");
            }else{
                System.out.println("yes");
            }
        }
    }
}