[Codility] Stacks and Queues - Brackets 풀이

예문

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

A string S consisting of N characters is considered to be properly nested if any of the following conditions is true:

S is empty; S has the form “(U)” or “[U]” or “{U}” where U is a properly nested string; S has the form “VW” where V and W are properly nested strings. For example, the string “{[()()]}” is properly nested but “([)()]” is not.

Write a function:

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

that, given a string S consisting of N characters, returns 1 if 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..200,000];
string S consists only of the following characters: "(", "{", "[", "]", "}" and/or ")".

해석

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

풀이

  • Stack 이용
  • 여는 괄호 (, {, [ push
  • 닫는 괄호 ), }, ] pop
  • 최종적으로 stack 이 비어있어야 함.

제약사항

  • N의 범위는 정수 [0..200,000]
  • 문자열 S는 “(“, “{“, “[”, “]”, “}”및 “)”문자로만 구성 됨.

코드

import java.util.Stack;
public int solution(String S) {
  Stack<Character> stack = new Stack<>();
  char lastChar;
  for (char c : S.toCharArray()) {
    if (c == '(' || c == '[' || c == '{') stack.push(c);
    else {
      if (stack.empty()) return 0;
      lastChar = stack.pop();

      if (c == ')' && lastChar != '(') return 0;
      else if (c == ']' && lastChar != '[') return 0;
      else if (c == '}' && lastChar != '{') return 0;
    }
  }
  return stack.isEmpty() ? 1 : 0;
}

결과