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의 괄호 짝이 맞지 않는다고 판단한다. 즉 여는 괄호의 등장은 상관없지만 닫는 괄호의 경우는 여는 괄호 순서의 역으로 맞춰서 등장해야 한다.

	def solution(S):
	stack = []
	parenDic = {'(':0, ')':0, '{':1, '}':1, '[':2, ']':2}
	for c in S:
	if c in ['(', '[', '{']:
	stack.append(c)
	else:
	if len(stack) == 0:
	return 0
	p = stack.pop()
	if parenDic[c] != parenDic[p]:
	return 0
	if len(stack) != 0:
	return 0
	else:
	return 1

view raw 7_2_Brackets.py hosted with ❤ by GitHub