Lesson7. Stacks and Queues - Nesting

Nesting - Determine whether a given string of parentheses (single type) is properly nested.

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

문제요약

길이 N의 문자열 S가 있을 때 다음 조건을 만족하면 nested라고 한다.

S는 빈문자열

S는 U가 nested일 경우 "(U)"형태

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

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

Assume that:

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

string S consists only of the characters "(" and/or ")".

Complexity:

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

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

풀이

스택을 활요하면 되나 괄호가 한 종류이므로 여는 괄호와 닫는 괄호의 수가 같은지만 확인해도 알 수 있다.

	def solution(S):
	leftCount = 0
	for c in S:
	if c == '(':
	leftCount += 1
	pass
	else:
	if leftCount > 0:
	leftCount -= 1
	else:
	return 0
	return 1 if leftCount == 0 else 0

view raw 7_1_Nesting.py hosted with ❤ by GitHub