BOJ - 2504 괄호의 값

leehyunjon·2022년 6월 30일

boj replaceAll 구현 문자열 자료구조

Algorithm

목록 보기

92/162

Problem

Solve

빡구현으로 하다가 너무 헷갈려서 다른 분의 풀이를 보다가 분배법칙 힌트를 얻어서 풀수 있었다.

(()[])인 경우 2*(2+3) = 2*2 + 2*3로 풀 수 있다.
초기에 ()는 2[]는 3으로 변경해준다면 (23)으로 변경할 수 있다.(replaceAll 사용)

열린 괄호 (, [인 경우 각 2,3을 뒤의 결과에 곱해준다.
숫자가 나온다면 곱해주는 값과 함께 결과값에 더해주면 된다.
닫힌 괄호 ), ]가 나오면 곱을 각 2,3을 제거해준다.
- 닫힌 괄호 경우의 수가 조금 까다로웠는데, temp에 2가 남았을때 temp/=2로 제거해주면 1이 남게 되어서 잘못된 연산을하게 된다. 그렇기 때문에 각 값을 제거해주었을 때 1이 나오게 되면 나눗셈이 아닌 뺄셈으로 temp의 값을 제거해주었다.

(()[])로 예를 들어보자면

( 인 경우 곱해줄 값 2를 추가한다.
숫자 2가 왔을 때 결과값에 곱해줄 값(temp)인 2를 곱해서 결과값에 4를 저장한다.
숫자 3이 왔을 때 두 수를 더해줘야하기 때문에 temp인 2를 곱해서 결과값 4에 2*3을 더해준다.
) 인 경우 분배가 끝났으므로 temp에서 2를 제거해준다.

이때 주의해야할 점은 올바른 괄호열이어야 한다는 점에서, 분기 반복문 전에 올바른 괄호열 여부를 먼저 확인하고 실행해주었다.

(()[[]])([])로 예를 들면 아래와 같다.

자세한 구현은 코드에서 설명하겠다.

Code

public class 괄호의값 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		String operation = br.readLine();

		Stack<Character> stack = new Stack<>();
		int temp = 0;
		int num = 0;

		//올바른 코드 라면
		if (isCorrect(operation)) {
        	//"()" = 2, "[]" = 2로 변경.
			operation = operation.replaceAll("\\[\\]", "3");
			operation = operation.replaceAll("\\(\\)", "2");
			for (char c : operation.toCharArray()) {
            	//스택이 비어있을 때
				if (stack.isEmpty()) {
                	//열린 괄호가 들어온다면 stack에 열린괄호를 넣어준다.
                    //올바른 괄호열을 확인했기때문에 비어있을때 닫힌 괄호는 들어오지 않는다.
					if (c == '[' || c == '(') {
						stack.push(c);
                        //각 괄호에 맞는 값을 곱해줄 값(temp)에 추가해준다.
                        //stack이 비어있는 경우 temp는 0이기 때문에 더해줘야한다.
						if (c == '[')
							temp += 3;
						if (c == '(')
							temp += 2;
					} else {
                    	//스택이 비어있을때 숫자가 들어온다면 temp는 0이므로 숫자만 결과값에 더해준다.
						int number = Integer.parseInt(String.valueOf(c));
						num += number;
					}

				} else {
					//열기괄호
					if (c == '[' || c == '(') {
						stack.push(c);
                        	//열기괄호인 경우 곱해줄 값(temp)에 각 값을 추가(곱)해준다.
							if (c == '[')
								temp *= 3;
							else
								temp *= 2;
					}
					//닫기 괄호
					else if (c == ']' || c == ')') {
						//']'
						if (c == ']') {
                        //닫기 괄호시 3만 남게 되면 나눗셈 결과가 1이 나오기 때문에 뺴기로 제거
                        //그 이상의 값이 남게 된다면 나눗셈으로 temp값 갱신
							if (temp / 3 == 1) {
								temp -= 3;
							} else {
								temp /= 3;
							}
						}
						//')'
                        //')' 닫기 괄호도 동일하다.
						else {
							if (temp / 2 == 1) {
								temp -= 2;
							} else {
								temp /= 2;
							}
						}
						stack.pop();
					}
					//숫자
					else {
                    	//괄호 안에서 숫자가 있을 시 temp의 값을 곱해서 결과값에 더해준다.
						int number = Integer.parseInt(String.valueOf(c));
						num += temp * number;
					}
				}
			}
		}

		bw.write(String.valueOf(num));
		bw.flush();
		bw.close();
	}

	//올바른 코드 여부
	static boolean isCorrect(String s) {
		Stack<Character> stack = new Stack<>();

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

		if (!stack.isEmpty()) {
			return false;
		}

		return true;
	}
}