코딩테스트/Baekjoon

[백준] 4949번: 균형잡힌 세상/ Java 11

soooy0 2025. 5. 29. 13:56

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

균형잡힌 세상

한국어   
시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB 171435 59066 45455 33.126%

문제

세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다.

정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다.

문자열에 포함되는 괄호는 소괄호("()") 와 대괄호("[]")로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다.

  • 모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다.
  • 모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다.
  • 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다.
  • 모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다.
  • 짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다.

정민이를 도와 문자열이 주어졌을 때 균형잡힌 문자열인지 아닌지를 판단해보자.

입력

각 문자열은 마지막 글자를 제외하고 영문 알파벳, 공백, 소괄호("( )"), 대괄호("[ ]")로 이루어져 있으며, 온점(".")으로 끝나고, 길이는 100글자보다 작거나 같다.

입력의 종료조건으로 맨 마지막에 온점 하나(".")가 들어온다.

출력

각 줄마다 해당 문자열이 균형을 이루고 있으면 "yes"를, 아니면 "no"를 출력한다.

 

1차 실패

/*
* 각 문장마다 해당 문자열이 (), [] 괄호 균형을 갖추고 있으면 "yes" 아니면 "no"를 출력한다.
* 1\. while 문이 !false 일 동안 반복
* 1-1. 만약 c[i] 가 '(' 혹은 '['와 같다면 스택에 push
* 1-2. 만약 c[i] 가 ')'일 경우
* 1-2-1. 만약 스택이 비어있고,  */

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main{
    public static void main(String[] args) throws IOException {

        // 입력값 받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // while 문 조건 변수
        boolean flag = false;
        // 종료조건인 온점 하나가 들어올 때까지 반복
        while(!flag){
            // 각 문장을 string 변수에 저장
            String line = br.readLine();

            //스택 생성
            Stack<Character> stack = new Stack<>();

            // 입력 종료 조건인 온점하나가 들어오면 반복문 종료
            if(line.equals(".")){
                break;
            }

            char[] c = line.toCharArray();

            for (char value : c) {
                if (value == '(' || value == '[') {
                    stack.push(value);
                } else if (value == ')') {
                    if(!stack.isEmpty() && stack.peek() == '('){
                        stack.pop();
                    } else {
                        continue;
                    }
                } else if (value == ']'){
                    if(!stack.isEmpty() && stack.peek() == '['){
                        stack.pop();
                    } else {
                        continue;
                    }
                }
            }

            if(stack.isEmpty()){
                System.out.println("yes");
            } else {
                System.out.println("no");
            }
        }

    }
}

 

1차 실수: 스택을 반복문 밖에서 생성하는 바람에, 이전에 남은 데이터들이 없어지지 않아 결과가 이상해짐.
2차 실수: 스택을 "()" 괄호용, "[]" 괄호용 2개를 생성해서 하는 바람에, 테케가 "([)]" 이렇게 주어질 경우에도 yes가 나오게 됨.
3차 실수: 스택에 ")" 닫는 괄호가 먼저 들어가면 그냥 break를 하도록 해둬서 스택이 비어있는 상황으로 반복문이 끝남. 따라서 no가 아닌 yes가 나오게 됨.
4차 실수: 위 1차 코드로 제출했으나 실패, 반례로 ")[]" "(])" 가 yes로 나오고 있는 상황.

 

성공 1번

  • 메서드 solve를 만들어서 return값에 따라 값을 출력하도록 바꾸어보았다.
  • 다시 코드 설계해서 차근차근 진행했더니 성공
/*
 * 각 문장마다 해당 문자열이 (), [] 괄호 균형을 갖추고 있으면 "yes" 아니면 "no"를 출력한다.
 * 1\. while 문이 true 일 동안 반복
 * 1-1. 만약 c[i] 가 '(' 혹은 '['와 같다면 스택에 push
 * 1-2. 만약 c[i] 가 ')'일 경우
 * 1-2-1. 만약 스택이 비어있을 경우엔 return false
 * 1-2-2. 만약 스택이 비어있지 않고, stack.peek() == '('과 같다면 stack.pop()
 * 1-2-2. 아니라면 return false
 * 1-3. 만약 c[i] 가 ']'일 경우 -> 동일하게 진행
 * 1-4. for 문이 종료되면, stack.isEmpty() 확인하여 true 면 "yes", false 면 "no" 출력
 * */

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main{
    public static void main(String[] args) throws IOException {

        // 입력값 받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        while(true){
            // 각 문장을 string 변수에 저장
            String line = br.readLine();

            // 입력 종료 조건인 온점하나가 들어오면 반복문 종료
            if(line.equals(".")){
                break;
            }

            // 메서드 호출
            if(solve(line)){
                System.out.println("yes");
            } else {
                System.out.println("no");
            }


        }

    }

    public static boolean solve(String line){
        //스택 생성
        Stack<Character> stack = new Stack<>();

        char[] c = line.toCharArray();

        for (char value : c) {
            // 여는 괄호일 경우
            if(value == '(' || value == '['){
                stack.push(value);
            }

            // 닫는 괄호일 경우
            if(value == ')'){
                if(stack.empty()){
                    return false;
                } else if (stack.peek() == '(') {
                    stack.pop();
                } else {
                    return false;
                }
            } else if(value == ']'){
                if(stack.empty()){
                    return false;
                } else if (stack.peek() == '[') {
                    stack.pop();
                } else {
                    return false;
                }
            }
        }

        return stack.isEmpty();
    }
}

 

 

성공 2번

/*
 * 각 문장마다 해당 문자열이 (), [] 괄호 균형을 갖추고 있으면 "yes" 아니면 "no"를 출력한다.
 * 1\. while 문이 true 일 동안 반복
 * 1-1. 만약 c[i] 가 '(' 혹은 '['와 같다면 스택에 push
 * 1-2. 만약 c[i] 가 ')'일 경우
 * 1-2-1. 만약 스택이 비어있을 경우엔 return false
 * 1-2-2. 만약 스택이 비어있지 않고, stack.peek() == '('과 같다면 stack.pop()
 * 1-2-2. 아니라면 return false
 * 1-3. 만약 c[i] 가 ']'일 경우 -> 동일하게 진행
 * 1-4. for 문이 종료되면, stack.isEmpty() 확인하여 true 면 "yes", false 면 "no" 출력
 * */

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main{
    public static void main(String[] args) throws IOException {

        // 입력값 받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        while(true){
            // 각 문장을 string 변수에 저장
            String line = br.readLine();

            // 입력 종료 조건인 온점하나가 들어오면 반복문 종료
            if(line.equals(".")){
                break;
            }

            // 메서드 호출
            if(solve(line)){
                System.out.println("yes");
            } else {
                System.out.println("no");
            }


        }

    }

    public static boolean solve(String line){
        //스택 생성
        Stack<Character> stack = new Stack<>();

        char[] c = line.toCharArray();

        for (char value : c) {
            // 여는 괄호일 경우
            if(value == '(' || value == '['){
                stack.push(value);
            }

            // 닫는 괄호일 경우
            if(value == ')'){
                if(stack.empty() || stack.peek() != '('){
                    return false;
                } else {
                    stack.pop();
                }
            } else if(value == ']'){
                if(stack.empty() || stack.peek() != '['){
                    return false;
                } else {
                    stack.pop();
                }
            }
        }

        return stack.isEmpty();
    }
}
  • 1번 성공코드의 if문 코드라인을 좀 간결하게 해보고 싶어서 바꿔봤는데

 

  • 오히려 시간이 증가함...!!! 논리연산자를 사용해서 그런가?
저작자표시 비영리 변경금지 (새창열림)