[Codility] Stacks and Queues - Nesting 풀이

예문

https://app.codility.com/programmers/lessons/7-stacks_and_queues/nesting/

A string S consisting of N characters is called properly nested if:

S is empty;
S has the form "(U)" where U is a properly nested string;
S has the form "VW" where V and W are properly nested strings.
For example, string "(()(())())" is properly nested but string "())" isn't.

Write a function:

class Solution { public int solution(String S); }

that, given a string S consisting of N characters, returns 1 if string S is properly nested and 0 otherwise.

For example, given S = “(()(())())”, the function should return 1 and given S = “())”, the function should return 0, as explained above.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [0..1,000,000];
string S consists only of the characters "(" and/or ")".

해석

  • S : N개의 문자들로 구성되어 있으며 아래 조건을 충족하면 중첩이다.
    • S는 비어있음
    • S는 “(U)” 형식을 가짐. U는 중첩 된 문자열
    • S는 “VW” 형식을 가짐. V와 W는 중첩 된 문자열
  • S가 중첩 되어 있으면 1. 그렇지 않으면 0을 반환하라!

풀이

  • 중첩이 되면 Stack에서 제거
  • Stack에 남아있으면 중첩이 아님.

제약사항

  • N의 범위는 정수 [0..1,000,000]
  • S의 문자는 “(“, “)” 으로만 구성되어 있음.

코드

import java.util.Stack;
public int solution(String S) {
  Stack<Character> stack = new Stack<>();
  char bracket;

  for (int i = 0; i < S.length(); i++) {
    bracket = S.charAt(i);

    if (stack.isEmpty()) {
      stack.push(bracket);
      continue;
    }

    if ('(' == stack.peek() && ')' == bracket) stack.pop();
    else stack.push(bracket);
  }
  return stack.size() > 0 ? 0 : 1;
}

결과