🥇 [Baekjoon / Java] 2504. 괄호의 값

문제 설명

---

💡 Info

• 난이도 : 골드 V
• 시간 제한 : 1초
• 메모리 제한 : 128MB
• 백준 링크: https://www.acmicpc.net/problem/2504
• 풀이 링크(GitHub): hayannn/CodingTest_Java/백준/Gold/2504. 괄호의 값

내용

4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다.

1. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다.
2. 만일 X가 올바른 괄호열이면 ‘(X)’이나 ‘[X]’도 모두 올바른 괄호열이 된다.
3. X와 Y 모두 올바른 괄호열이라면 이들을 결합한 XY도 올바른 괄호열이 된다.

예를 들어 ‘(()[[]])’나 ‘(())[][]’ 는 올바른 괄호열이지만 ‘([)]’ 나 ‘(()()[]’ 은 모두 올바른 괄호열이 아니다.

우리는 어떤 올바른 괄호열 X에 대하여 그 괄호열의 값(괄호값)을 아래와 같이 정의하고 값(X)로 표시한다.

1. ‘()’ 인 괄호열의 값은 2이다.
2. ‘[]’ 인 괄호열의 값은 3이다.
3. ‘(X)’ 의 괄호값은 2×값(X) 으로 계산된다.
4. ‘[X]’ 의 괄호값은 3×값(X) 으로 계산된다.
5. 올바른 괄호열 X와 Y가 결합된 XY의 괄호값은 값(XY)= 값(X)+값(Y) 로 계산된다.

예를 들어 ‘(()[[]])([])’ 의 괄호값을 구해보자.

‘()[[]]’ 의 괄호값이 2 + 3×3=11 이므로 ‘(()[[]])’의 괄호값은 2×11=22 이다.

그리고 ‘([])’의 값은 2×3=6 이므로 전체 괄호열의 값은 22 + 6 = 28 이다.

여러분이 풀어야 할 문제는 주어진 괄호열을 읽고 그 괄호값을 앞에서 정의한대로 계산하여 출력하는 것이다.

📥입력 조건

• 첫째 줄에 괄호열을 나타내는 문자열(스트링)이 주어진다. 단 그 길이는 1 이상, 30 이하이다.
  

(()[[]])([])

[][]((])

📤출력 조건

• 첫째 줄에 그 괄호열의 값을 나타내는 정수를 출력한다. 만일 입력이 올바르지 못한 괄호열이면 반드시 0을 출력해야 한다.
  

28

0

문제 이해

---

• 괄호열에 각각 배당된 숫자에 맞게 값을 구하기
  • 단, 올바른 괄호열이 아닌 경우 → 반드시 0 출력!

알고리즘

---

실제 풀이 시간 : 35분

• 입력
  • String List 입력받기
• 계산
  • 기호 ( → opencount 세기
  • 기호 ) → closecount 세기
    • 두 count가 일치해야 올바른 문자열
    • 그렇지 않은 경우, 0 반환
  • 기호 [ → opencount 세기
  • 기호 ] → closecount 세기
    • 두 count가 일치해야 올바른 문자열
    • 그렇지 않은 경우, 0 반환
  • 결과 값 : 기호 (,) 개수 곱 + 기호 [,] 개수 곱
    • 기호 (, ) : count*2
    • 기호 [, ] : (count + 1)*count
• 출력
  • 결과 값 출력하기

package BJ;

import java.util.*;

public class BJ2504 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		String List = sc.nextLine();
		
		int openCntS = 0;
		int closeCntS = 0;
		
		int openCntL = 0;
		int closeCntL = 0;
		
		int result = 0;
		
		for(int i=0; i<List.length(); i++) {
			if(List.charAt(i) == '(') openCntS++;
			
			if(List.charAt(i) == ')') closeCntS++;
		
			if(List.charAt(i) == '[') openCntL++;
		
			if(List.charAt(i) == ']') closeCntL++;
		
		}
		
		if(openCntS == closeCntS && openCntL == closeCntL) {
			result = (openCntS*2) + ((openCntL+1)*3);
		} else {
			result = 0;
		}
		System.out.println(result);
	}

}

오답 체크

---

• 원하는 값이 아닌 다른 수가 나오는 문제 발생
  • 괄호의 수를 세는 대신, 스택을 사용하여 코드를 재구성해 해결

//before
if(List.charAt(i) == '(') openCntS++;
			
if(List.charAt(i) == ')') closeCntS++;

if(List.charAt(i) == '[') openCntL++;

if(List.charAt(i) == ']') closeCntL++;

}

//after
/*여는 괄호인 경우
	- 해당 괄호를 스택에 push
	- temp *2 또는 *3하기
	*/
	if(List.charAt(i) == '(') {
		stack.push(List.charAt(i));
		temp *= 2;
	}
	if(List.charAt(i) == '[') {
		stack.push(List.charAt(i));
		temp *= 3;
	}
	
	
	/*닫는 괄호인 경우
	 - 스택이 비어있고  + 스택 맨 위에 있는 괄호와 현재 괄호가 매치되지 않는다면(peek로 확인)
	 -> 올바르지 않은 문자열로 보고 빠져나가기
	 */
	if(List.charAt(i) == ')' && (stack.isEmpty() || stack.peek() != '(')) {
		isValid = false;
		break;
	}
	if(List.charAt(i) == ']' && (stack.isEmpty() || stack.peek() != '[')) {
		isValid = false;
		break;
	}
	
	
	
	/*올바른 괄호열이 성립되는 경우
	 - 이전에 여는 괄호가 같은 종류의 괄호였는지 확인 -> 해당 괄호에 할당된 값을 결과에 더하기
	 - 스택에서 괄호를 pop
	 - 임시 값 temp를 해당 괄호의 규칙에 맞게 /=2 또는 /=3
	*/
	if(List.charAt(i) == ')') {
		if(List.charAt(i-1) == '(')
			result += temp;
		stack.pop();
		temp /= 2;
	}
	if(List.charAt(i) == ']') {
		if(List.charAt(i-1) == '[')
			result += temp;
		stack.pop();
		temp /= 3;
	}
}

• 결과 값 계산

//before
if(openCntS == closeCntS && openCntL == closeCntL) {
	result = (openCntS*2) + ((openCntL+1)*3);
} else {
result = 0;
}

//after
if(!isValid || !stack.isEmpty()) { //!(올바른 괄호열) 즉, 올바르지 않은 괄호열이거나 스택이 비어있지 않은 경우 결과는 0 출력
	result = 0;
}

최종 풀이

---

• 개념 참고

[BOJ] 백준 2504번 괄호의 값 (Java)

실제 풀이 시간 : 1시간 38분(첫 풀이 포함)

• 입력
  • 괄호열 List 입력받기
• 계산
  • Stack 선언
  • 임시 값 temp, 최종 값 result 지정
  • 여는 괄호
    • 해당 괄호를 스택에 push
    • temp 2 또는 3하기
  • 닫는 괄호
    • 스택이 비어있고 + 스택 맨 위에 있는 괄호와 현재 괄호가 매치되지 않는다면(peek로 확인) -> 올바르지 않은 문자열로 보고 빠져나가기
  • 괄호열 성립 여부 조사
    • 올바른 괄호열이 성립되는 경우
      • 이전에 여는 괄호가 같은 종류의 괄호였는지 확인 -> 해당 괄호에 할당된 값을 결과에 더하기
      • 스택에서 괄호를 pop
      • 임시 값 temp를 해당 괄호의 규칙에 맞게 /=2 또는 /=3
• 출력
  • 결과 값 출력하기
    • (올바른 괄호열) 즉, 올바르지 않은 괄호열이거나 스택이 비어있지 않은 경우 결과는 0 출력

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		String List = sc.nextLine();
		
		Stack<Character> stack = new Stack<>();
		int result = 0;
		int temp = 1; //임시 값은 괄호가 여는 괄호일 경우 2로, 여는 대괄호일 경우 3으로 초기화
		boolean isValid = true; //올바른 괄호 쌍이 입력되었는지 여부 확인
		
		for(int i=0; i<List.length(); i++) {
			
			/*여는 괄호인 경우
			- 해당 괄호를 스택에 push
			- temp *2 또는 *3하기
			*/
			if(List.charAt(i) == '(') {
				stack.push(List.charAt(i));
				temp *= 2;
			}
			if(List.charAt(i) == '[') {
				stack.push(List.charAt(i));
				temp *= 3;
			}
			
			
			/*닫는 괄호인 경우
			 - 스택이 비어있고  + 스택 맨 위에 있는 괄호와 현재 괄호가 매치되지 않는다면(peek로 확인)
			 -> 올바르지 않은 문자열로 보고 빠져나가기
			 */
			if(List.charAt(i) == ')' && (stack.isEmpty() || stack.peek() != '(')) {
				isValid = false;
				break;
			}
			if(List.charAt(i) == ']' && (stack.isEmpty() || stack.peek() != '[')) {
				isValid = false;
				break;
			}
			
			
			
			/*올바른 괄호열이 성립되는 경우
			 - 이전에 여는 괄호가 같은 종류의 괄호였는지 확인 -> 해당 괄호에 할당된 값을 결과에 더하기
			 - 스택에서 괄호를 pop
			 - 임시 값 temp를 해당 괄호의 규칙에 맞게 /=2 또는 /=3
			*/
			if(List.charAt(i) == ')') {
				if(List.charAt(i-1) == '(')
					result += temp;
				stack.pop();
				temp /= 2;
			}
			if(List.charAt(i) == ']') {
				if(List.charAt(i-1) == '[')
					result += temp;
				stack.pop();
				temp /= 3;
			}
		}
		
		
		
		
		if(!isValid || !stack.isEmpty()) { //!(올바른 괄호열) 즉, 올바르지 않은 괄호열이거나 스택이 비어있지 않은 경우 결과는 0 출력
			result = 0;
		}
		System.out.println(result);
	}
}