[프로그래머스💯] 코딩테스트 연습 > 스택/큐 > 탐욕법

<프로그래머스 문제풀이>

 

풀이)

이 문제는 '()' 가 나왔을 때 레이저를  쏜다. 레이저를 쏘는 시점에 쌓여있던 막대기 수 만큼 부분 막대기가 생성될 것이고, '()' 가 아닌 '))' (이전 문자가 '(' 인 경우) 이라면 막대기 층이 하나 낮아지므로 막대기가 1개 의 부분막대기가 생성된다. 

 

요약하자면 ')' 가 나왔을 때

case A <'()' 인 경우> : 쌓여있던 막대기 수-1 만큼 블럭 result를 늘려준다.

- 막대기 수 - 1 인 이유는 '()' 에서 나오는 '(' 도 쌓인 막대기로 계산한다고 가정 때문.

case B <'))' 인 경우> : result 를 1만큼만 늘려주고 막대기를 하나 줄인다.

 

 

def solution(arrangement):
    stk = [] 
    count = 0       # 스택에 들어가있는 ( 수
    recent = 0      # 이전 문자가 '(' = 0, ')' = 1
    res = 0
    for i in arrangement:
        # case A
        if i=="(" :
            stk.append(count)
            count += 1
            recent = 0
        # case B
        elif i==")" :

            # 괄호 짝 안맞을때
            if stk == [] :
                print("error")
                break
            else:
                if recent == 0: 
                    res += stk.pop()
                else:
                    stk.pop()
                    res += 1
            recent = 1
            count -= 1
    return res

 

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges