[알고리즘] 쇠막대기

1. 문제

2. 나의 풀이

def solution(arrangement):
    answer = 0
    stack = []
    for i in range(len(arrangement)) :
        if arrangement[i] == "(" :
            stack.append(0)
        else :
            temp = stack.pop()
            if not temp :
                if stack != [] : stack[-1] += (temp+1)
            elif temp > 0 : 
                answer += (temp+1)
                if stack != [] : stack[-1] += temp
    return answer

생각보다 어려웠던 문제였다. 아직 많이 부족하고 또, stack을 다루는 기술이 적다는 것을 알았다. 위 코드의 알고리즘은 레이저를 발견할 때마다 stack 에 쌓여있는 값들에 +1 을 해주는 것이다. 그런데 위 알고리즘은 테스트 1에서 계속 시간 초과가 나서 문제가 발생하였다.

def solution(arrangement):
    answer = 0
    stack = []
    for i in range(len(arrangement)) :
        if arrangement[i] == "(" :
            stack.append(0)
        else :
            temp = stack.pop()
            if not temp :
                for j in range(len(stack)) : stack[j] += 1
            else : answer += (temp+1)
    return answer

다음은 테스트 1에서 시간초과가 났던 초기 코드이다. 시간초과가 나서 고민하던 중 다음과 같은 답변을 보았다.

stack 안에 있는 모든 값에 1을 더해주는 것이 아닌, 맨뒤의 값에만 저장을 하면 시간초과가 해결되었다.

3. 다른사람의 풀이

def solution(arrangement):
    answer = 0
    stack = 0
    laseron = False
    for p in arrangement:
        if p == '(':
            laseron = True
            stack += 1
        else:
            if laseron==True:
                answer += stack-1
                laseron=False
            else:
                answer += 1
            stack -= 1
    return answer

위 알고리즘에서 핵심은 ) 가 들어오는 경우를 () 인 경우와 ))인 경우 두가지로 나눈 것이다. 다음 그림을 통해 더 쉽게 설명할 수 있다.
저기서 빨간색은 ()인 경우, 파란색은 ))인 경우 생성되는 쇠 막대기를 나타낸 것이다. ()인 경우는 그간 stack에 쌓여있는 (괄호의 개수-1 만큼 쇠막대기가 생성되고 )) 인 경우에는 단 하나의 쇠막대기가 생성된다는 것을 알 수 있다. 정말 이세상에는 똑똑한 사람들이 많다…

4. 배운점

프로그래머스 테스트에서 시간초과가 나면 시간초과라고 알려주는 걸 처음알았다!! 그리고 아직 문제푸는 능력이 많이 부족하다…