티스토리 뷰

728x90
반응형

소스 코드는 여기 있습니다.
문제는 여기 있습니다.

Problem

Given a balanced parentheses string s, return the score of the string.

The score of a balanced parentheses string is based on the following rule:

"()" has score 1.
AB has score A + B, where A and B are balanced parentheses strings.
(A) has score 2 * A, where A is a balanced parentheses string.

Example 1:

Input: s = "()"
Output: 1

Example 2:

Input: s = "(())"
Output: 2

Example 3:

Input: s = "()()"
Output: 2

Constraints:

  • 2 <= s.length <= 50
  • s consists of only '(' and ')'.
  • s is a balanced parentheses string.

Solution

괄호가 주어질 때 점수를 매기는데 일반 괄호는 1점을, 중첩된 괄호는 2배의 점수를 얻을 수 있을 때 점수를 구하는 문제입니다.

package io.lcalmsky.leetcode.score_of_parentheses;

public class Solution {

  public int scoreOfParentheses(String s) {
    Stack<Integer> stack = new Stack<>();
    stack.push(0);
    for (int i = 0; i < s.length(); i++) {
      if (s.charAt(i) == '(') {
        stack.push(0);
      } else {
        int x = stack.pop();
        int y = stack.pop();
        stack.push(y + Math.max(2 * x, 1));
      }
    }
    return stack.pop();
  }
}

스택으로 점수를 계산하는데 처음에 초기 값인 0을 먼저 push하고, 괄호가 열릴 때마다 0을 push 합니다.

괄호가 닫힐 때마다 스택에서 두 개의 원소를 pop 해준 뒤 가장 최근 값에 두 배를 한 것과 1중 더 높은 값과 그 다음 최근 값을 반복해서 더해주면 괄호의 점수를 계산할 수 있습니다.

위 방법이 이해하기는 쉬운데 성능은 매우 저조하게 나와서 다른 답을 찾아보았습니다.

class Solution {

  public int scoreOfParentheses(String s) {
    int score = 0;
    int depth = 0;
    for (int i = 0; i < s.length(); i++) {
      if (s.charAt(i) == '(') {
        depth++;
      } else {
        depth--;
      }
      if (s.charAt(i) == ')' && s.charAt(i - 1) == '(') {
        score += Math.pow(2, depth);
      }
    }
    return score;
  }
}

여기선 depth로 괄호의 중첩 정도를 계산하였습니다.

depth가 0일 때 중첩된 괄호가 없으므로 2^0인 1이 되고, 중첩된 괄호가 많을 수록 2^n이 더해지게 됩니다.

Test

package io.lcalmsky.leetcode.score_of_parentheses;

import static org.junit.jupiter.api.Assertions.assertAll;
import static org.junit.jupiter.api.Assertions.assertEquals;

import org.junit.jupiter.api.Test;

class SolutionTest {

  @Test
  void givenParentheses_whenCompute_thenCorrect() {
    assertAll(
        () -> test("()", 1),
        () -> test("(())", 2),
        () -> test("()()", 2),
        () -> test("(()(()))", 6)
    );
  }

  private void test(String given, int expected) {
    // when
    Solution solution = new Solution();
    int actual = solution.scoreOfParentheses(given);

    // then
    assertEquals(expected, actual);
  }
}
728x90
반응형

'Algorithm > LeetCode Daily Challenge' 카테고리의 다른 글

991. Broken Calculator  (0) 2022.04.26
289. Game of Life  (0) 2022.04.25
856. Score of Parentheses  (0) 2022.04.24
31. Next Permutation  (0) 2022.04.23
344. Reverse String  (0) 2022.04.22
1046. Last Stone Weight  (0) 2022.04.19
댓글
댓글쓰기 폼