[백준] 4949번 : 균형잡힌 세상 - JAVA [자바]

 
www.acmicpc.net/problem/4949

4949번: 균형잡힌 세상

 

 

---

• 문제

 

 

 

 

이전 괄호 문제에서 좀 더 업그레이드 된 버전이다.

 

 

 

 

 

 

 

 

 

---

• 알고리즘 [접근 방법]

 

 

이 문제는 이 전 문제인 9012의 괄호 문제를 정확히 이해하고 있다면 쉽게 풀 수 있을 것이다. 만약 괄호 문제를 풀어보지 않았다면 먼저 아래 포스팅을 먼저 보고 오시길 바란다.

 

 

[백준] 9012번 : 괄호 - JAVA [자바]

 

 

 

 

 

 

 

우리가 괄호 문제에서 풀었을 때는 '(' 와 ')' 만 다루었었다.

 

이 때, 온전한 수식을 검사하는 코드를 다음과 같이 짰었다.

 

String s = input();	// 한 줄 입력
for(int i = 0; i < length; i++) {	// legnth는 문자열의 길이
 
	char c = s.charAt(i);	// i 번째 문자
    
	// 여는 괄호일 경우 스택에 넣는다.
	if(c == '(') {
		stack.push(c);
	}
 
	// 아래는 모두 닫는 괄호 일 경우들이다.
    
	// 스택이 비어있는 경우. 즉, 닫는 괄호를 입력받았으나 pop할 원소가 없을 경우
	else if(stack.empty()){
		return "NO";
	}
	// 그 외의 경우 stack 원소를 pop 한다.
	else {
		stack.pop();
	}
}
 
/*
 모든 검사 마치고 스택에 잔여 요소가 있으면 여는 괄호가 많은 경우는 "NO"
 스택이 비어있으면 온전한 수식이므로 "YES" 이다.
*/
 
if(stack.empty()) {
	return "YES";
}
else {
	return "NO";
}

 

 

그러면 위 문제에서 수정해야 할 것은 무엇일까?

 

먼저 이전 문제랑 달라진 점을 보자.

 

1. 대괄호 '[' 와 ']' 가 추가되었다.

2. 괄호와 상관 없는 문자들이 섞여있다.

 

우리가 균형잡힌 문자열인지 판단할 때 '괄호 문자'인지를 판단해야하고, 이 후  '여는 괄호'인지, '닫는 괄호'인지를 판단하며, 닫는 괄호 일 경우 ']' 의 경우는 '[' 과 매칭되어야 하고, ')' 의 경우는 '(' 과 매칭되어야 한다.

그리고 괄호가 아닌 문자의 경우에는 그냥 넘어가면 된다.

 

즉, 약간의 수정만하여 다음과 같이 짜면 된다.

 

String s = input();	// 한 줄 입력
for(int i = 0; i < s.length(); i++) {
			
	char c = s.charAt(i);	// i 번째 문자 
			
	// 여는 괄호일 경우 스택에 push 
	if(c == '(' || c == '[') {
		stack.push(c);
	}
			
	// 닫는 소괄호 일 경우 
	else if(c == ')') {
				
		// 스택이 비어있거나 pop할 원소가 소괄호랑 매칭이 안되는 경우 
		if(stack.empty() || stack.peek() != '(') {
			return "no";
		}
		else {
			stack.pop();
		}
	}
			
	else if(c == ']') {
				
		// 스택이 비어있거나 pop할 원소가 대괄호랑 매칭이 안되는 경우 
		if(stack.empty() || stack.peek() != '[') {
			return "no";
		}
		else {
			stack.pop();
		}
	}
			
	// 그 외의 경우에는 불필요한 문자들이기에 skip한다. 
}
		
if(stack.empty()) {
	return "yes";
}
else {
	return "no";
}

 

 

 

 

 

 

 

 

 

 

 

 

 

 

---

• 4가지 방법을 사용하여 풀이한다.

 

위 에서 설명한 방법은 Stack 클래스를 사용한 방법이다. 위 알고리즘에서 Stack의 원리를 char[] 배열로도 구현할 수 있는데, 그리 어렵지도 않고, Stack 구현만 할 줄 안다면 매우 쉽게 풀이할 수 있는지라 따로 설명하지는 않았다.

 

즉, Stack클래스를 사용한 것과 char[] 배열을 사용한 방법에 각각 입력의 방법을 달리하여 풀어보기로 하겠다.

 

1. Scanner + Stack

2. BufferedReader + Stack

3 . Scanner + char[]

4. BufferedReader + char[]

 

 

 

 

---

• 풀이

- 방법 1 : [Scanner + Stack]

 

import java.util.Scanner;
import java.util.Stack;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);

		String s;
		
		while(true) {		
			s = in.nextLine();
			
			if(s.equals(".")) {	// 종료 조건문 
				break;
			}		
			System.out.println(solve(s));
		}
	
	}
	
	public static String solve(String s) {
		
		Stack<Character> stack = new Stack<>();
		
		for(int i = 0; i < s.length(); i++) {
			
			char c = s.charAt(i);	// i 번째 문자 
			
			// 여는 괄호일 경우 스택에 push 
			if(c == '(' || c == '[') {
				stack.push(c);
			}
			
			// 닫는 소괄호 일 경우 
			else if(c == ')') {
				
				// 스택이 비어있거나 pop할 원소가 소괄호랑 매칭이 안되는 경우 
				if(stack.empty() || stack.peek() != '(') {
					return "no";
				}
				else {
					stack.pop();
				}
			}
			
			else if(c == ']') {
				
				// 스택이 비어있거나 pop할 원소가 대괄호랑 매칭이 안되는 경우 
				if(stack.empty() || stack.peek() != '[') {
					return "no";
				}
				else {
					stack.pop();
				}
			}
			
			// 그 외의 경우에는 불필요한 문자들이기에 skip한다. 
		}
		
		if(stack.empty()) {
			return "yes";
		}
		else {
			return "no";
		}
	}

}

 

 

가장 기본적인 방법이라 할 수 있겠다.

 

 

 

---

- 방법 2 : [BufferedReader + Stack]

 

 

 

입력 방법을 Scanner 대신 BufferedReader 을 사용하여 풀이하는 방법이다. 추가로 성능개선차 출력방법을 조금 다르게 StringBuilder를 사용하였다.

 

 

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		String s;
		
		while(true) {
			
			s = br.readLine();
			
			if(s.equals(".")) {	// 종료 조건문 
				break;
			}
			
			sb.append(solve(s)).append('\n');
		}
		
		System.out.println(sb);
		
		
	}
	
	public static String solve(String s) {
		
		Stack<Character> stack = new Stack<>();
		
		for(int i = 0; i < s.length(); i++) {
			
			char c = s.charAt(i);	// i 번째 문자 
			
			// 여는 괄호일 경우 스택에 push 
			if(c == '(' || c == '[') {
				stack.push(c);
			}
			
			// 닫는 소괄호 일 경우 
			else if(c == ')') {
				
				// 스택이 비어있거나 pop할 원소가 소괄호랑 매칭이 안되는 경우 
				if(stack.empty() || stack.peek() != '(') {
					return "no";
				}
				else {
					stack.pop();
				}
			}
			
			else if(c == ']') {
				
				// 스택이 비어있거나 pop할 원소가 대괄호랑 매칭이 안되는 경우 
				if(stack.empty() || stack.peek() != '[') {
					return "no";
				}
				else {
					stack.pop();
				}
			}
			
			// 그 외의 경우에는 불필요한 문자들이기에 skip한다. 
		}
		
		if(stack.empty()) {
			return "yes";
		}
		else {
			return "no";
		}
	}

}

 

 

 

 

 

 

 

---

- 방법 3 : [Scanner + char[]]

 

 

 

스택 클래스 대신 배열을 선언하고 이를 스택처럼 사용하는 방법도 있다. 따로 설명은 하지 않았지만, 스택의 원리를 그대로 따라가기 때문에 코드만 보더라도 쉽게 이해할 수 있을 것이다.

 

 

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
    
		Scanner in = new Scanner(System.in);
		StringBuilder sb = new StringBuilder();
		String s;

		while (true) {

			s = in.nextLine();

			if (s.equals(".")) { // 종료 조건문
				break;
			}

			sb.append(solve(s)).append('\n');
		}

		System.out.println(sb);
	}

	public static String solve(String s) {
		
		char[] stack = new char[s.length()];	// 스택처럼 사용할 비열 
		int size = 0;

		for (char val : s.toCharArray()) {
			
			// 여는 괄호일 경우 배열에 저장 후 size 1증가 
			if (val == '(' || val == '[') {
				stack[size] = val;
				size++;
			} 
			
			// 닫는 소괄호일경우 
			else if (val == ')') {
				
				// 요소가 비어있거나 pop할 원소가 소괄호랑 매칭이 안되는 경우 
				if (size == 0 || stack[size - 1] != '(') {
					return "no";
				} 
				else {
					size--;
				}
			} 
			
			// 닫는 소괄호일경우 
			else if (val == ']') {
				
				// 요소가 비어있거나 pop할 원소가 소괄호랑 매칭이 안되는 경우 
				if (size == 0 || stack[size - 1] != '[') {
					return "no";
				} 
				else {
					size--;
				}
			}
		}
		
		if (size != 0) {
			return "no";
		} 
		else {
			return "yes";
		}
	}
}

 

 

물론 pop할 때 char[] 배열에 명시적으로 문자를 0 값으로 치환해주어도 되나 size로 카운팅만 해주어도 크게 문제되진 않는다.

 

 

 

---

- 방법 4 : [BufferedReader + char[]]

 

 

 

방법 3에서 입력 방법만 바꾼 것이라 크게 다를 것은 없다.

 

 

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		String s;

		while (true) {

			s = br.readLine();

			if (s.equals(".")) { // 종료 조건문
				break;
			}

			sb.append(solve(s)).append('\n');
		}

		System.out.println(sb);
	}

	public static String solve(String s) {
		
		char[] stack = new char[s.length()];	// 스택처럼 사용할 비열 
		int size = 0;

		for (char val : s.toCharArray()) {
			
			// 여는 괄호일 경우 배열에 저장 후 size 1증가 
			if (val == '(' || val == '[') {
				stack[size] = val;
				size++;
			} 
			
			// 닫는 소괄호일경우 
			else if (val == ')') {
				
				// 요소가 비어있거나 pop할 원소가 소괄호랑 매칭이 안되는 경우 
				if (size == 0 || stack[size - 1] != '(') {
					return "no";
				} 
				else {
					size--;
				}
			} 
			
			// 닫는 소괄호일경우 
			else if (val == ']') {
				
				// 요소가 비어있거나 pop할 원소가 소괄호랑 매칭이 안되는 경우 
				if (size == 0 || stack[size - 1] != '[') {
					return "no";
				} 
				else {
					size--;
				}
			}
		}
		
		if (size != 0) {
			return "no";
		} 
		else {
			return "yes";
		}
	}
}

 

 

 

 

 

 

 

 

 

 

 

 

---

• 성능

 

 

 

채점 번호 : 24142208  -  방법 4 : BufferedReader + char[]

채점 번호 : 24142206  -  방법 3 : Scanner + char[]

채점 번호 : 24142175  -  방법 2 : BufferedReader + Stack

채점 번호 : 24142166  -  방법 1 : Scanner + Stack

 

 

입력의 경우는 확실히 Scanner 보다는 BufferedReader 가 빠른 걸 볼 수 있다. 또한 Stack 클래스를 쓰는 것보다는 단순 배열로 처리하는 것이 메모리나 처리 과정에서 단순화 되어있어 더 빠르다는 것을 볼 수 있다.

 

 

---

• 정리

 

 

저 번 문제만 풀었다면 어렵지 않게 풀 수 있는 문제라 매우 쉽게 풀었을 것이다.

 

아마 스택의 원리를 이해하지 못하고 그냥 풀어서 그런지 정답률이 생각 외로 낮다만.. 만약 스택에 대해 궁금하다면 아래 포스팅을 참고하셔도 좋을 것 같다.

 

자바 [JAVA] - Stack (스택) 구현하기

 

혹여 어렵거나 이해가 가지 않는 부분이 있다면 댓글 남겨주시면 된다. 빠르게 답변드리도록 하겠다.