7-1. 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 is made only of the following characters: '(', '{', '[', ']', '}' and/or ')'.
문자열 S가 다음 조건 중 하나를 만족하면 올바르게 중첩된 것으로 간주됩니다:
S가 비어 있습니다.
S가 “(U)” 또는 “[U]” 또는 “{U}” 형태를 가지며, 여기서 U는 올바르게 중첩된 문자열입니다.
S가 “VW” 형태를 가지며, 여기서 V와 W는 올바르게 중첩된 문자열입니다.
예를 들어, 문자열 "{[()()]}"는 올바르게 중첩된 것이지만 "([)()]"는 그렇지 않습니다.
N개의 문자로 구성된 문자열 S가 주어졌을 때, S가 올바르게 중첩된 경우 1을 반환하고 그렇지 않은 경우 0을 반환합니다.
예를 들어, S = "{[()()]}"가 주어지면 함수는 1을 반환해야 하고, S = "([)()]"가 주어지면 함수는 0을 반환해야 합니다.
다음 가정을 위한 효율적인 알고리즘을 작성하세요:
N은 [0…200,000] 범위 내의 정수입니다.
문자열 S는 ‘(’, ‘{’, ‘[’, ‘]’, ‘}’ 및/또는 ‘)’ 문자로만 구성됩니다.
즉 괄호가 전부 올바르게 닫히는 경우에는 1을 반환
괄호가 올바르게 닫히지 않는 경우에는 0을 반환하면 됩니다.
문제풀이
import java.util.*;
class Solution {
public int solution(String S) {
Stack<Character> stack = new Stack<>();
for (char ch : S.toCharArray()) {
if (ch == '{' || ch == '[' || ch == '(') {
stack.push(ch);
} else {
if (stack.isEmpty()) {
return 0;
}
char last = stack.pop();
if ((ch == '}' && last != '{') ||
(ch == ']' && last != '[') ||
(ch == ')' && last != '(')) {
return 0;
}
}
}
return stack.isEmpty() ? 1 : 0;
}
}
스택을 사용하여 짝이 맞는지 확인
" {, [, ( "일 경우에는 스택에 푸시
" }, ], ) "일 경우에는 짝이 맞는지 확인 후
짝이 맞지 않으면 0을 반환
제출결과
문제풀어보기 -> https://app.codility.com/programmers/lessons/7-stacks_and_queues/brackets/
