[프로그래머스] 쇠막대기

문제 보기

이 문제는 스택/큐 문제이다.

문제를 해결하는데 스택이 사용되긴 했지만, 오히려 개념은 DP에 가까운 느낌이다.

문자열을 하나씩 읽을 때마다, 레이저를 만나게 되면 잘린 막대기가 몇 개인지 판단하였다.

 

문제를 푼 로직은 다음과 같다.

1. 레이저는 "()"로 구분되므로, 더 쉬운 이해를 위해서 다른 문자 하나로 치환한다. (나의 경우 '.'로 치환했다.)
2. 문자열을 읽으면서 '('를 만나면 막대기를 현재에서 한 개 더 올린다는 뜻이므로, '('를 만날 때마다 스택에 추가하고, 쇠막대기의 개수를 한 개 더한다. (7~9번째 줄)
3. 문자열을 읽으면서 ')'를 만나면 젤 위의 막대기가 끝이 났다는 뜻이다. 그러므로 스택에 추가한 '('를 한 개 뺀다. (10~11번째 줄)
4. '.'를 만나면 (=레이저를 만나면) 현재 쌓여있는 막대기가 이등분이 되므로, 현재 스택의 길이(높이)만큼 한 번 더 더해준다. (12~13번째 줄)

 

def solution(arrangement):
	answer = 0
	replaced = arrangement.replace('()', '.')
	stack = list()
	
	for i, c in enumerate(replaced):
		if c == '(':
			stack.append(c)
			answer += 1
		elif c == ')':
			stack.pop()
		else:
			answer += len(stack)
	
	return answer