Lesson7. Stacks and Queues - Brackets

Brackets - Determine whether a given string of parentheses (multiple types) is properly nested.

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

문제요약

길이 N인 문자열 S가 다음의 형태일 때 nested라고 한다.

S는 빈문자열

S는 U가 nested일 때 "(U)" 또는 "[U]" 또는 "{U}"의 형태

S는 V와 W가 nested일 때 "VW"의 형태

주어진 문자열 S가 nested이면 1, 아니면 0을 반환한다. (괄호 짝 맞추기)

Assume that:

N is an integer within the range [0..200,000];

string S consists only of the following characters: "(", "{", "[", "]", "}" and/or ")".

Complexity:

expected worst-case time complexity is O(N);

expected worst-case space complexity is O(N) (not counting the storage required for input arguments).

풀이

전형적인 괄호 짝 맞추기로 stack을 이용하면 된다. 여는 괄호를 만나면 stack에 넣고 닫는 괄호를 만나면 stack에서 꺼낸다. 단 stack에서 꺼낼게 없거나 꺼낸 괄호가 짝이 맞지 않거나, 전체 처리 후 stack에 여는 괄호가 남아 있다면 해당 string의 괄호 짝이 맞지 않는다고 판단한다. 즉 여는 괄호의 등장은 상관없지만 닫는 괄호의 경우는 여는 괄호 순서의 역으로 맞춰서 등장해야 한다.