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

문제 설명

문제에서 그림과 함께 잘 설명되어 있기에 pass

봐야할 것이라면

1. 잘린 쇠막대기의 총 수를 구하라

2. '()'가 레이저.

3. arrangement가 최대 10만이기에 시간초과 주의

접근

딱 보면 뭐 어떻게 해야하는거야... 싶은 문제다.

그래서 나는 문제를 단순화해서 생각해봤다. 단순화할 때 유념해야할 것은 '()'가 레이져, 잘린 갯수 구하는 문제라는 것.

case 1. ()만 주어질 경우

잘린 쇠막대기가 없으므로 0

case2. (())

잘린 쇠막대기가 레이저에 의해 2개가 된다.

case3. ((()))

잘린 쇠막대기가 레이저에 의해 4개가 된다.

case4. (()())

잘린 쇠막대기가 레이저에 의해 3개가 된다.

case5. ((()()))

잘린 쇠막대기가 레이저에 의해 6개가 된다.

case6. ( () (()) )

잘린 쇠막대기가 레이저에 의해 5개가 된다.

이쯤되면 규칙이 보일랑말랑할 것이다.

1. stack에 '('를 담는다면,

2. 레이저를 만날 때 stack의 크기만큼 조각이 늘어나고,

3. 만약 ')'만을 만난다면 조각이 1개만큼 늘어난다.

그런데 arrangement를 1개씩 본다 했을 때 ')'을 만난 경우 레이저인지 남은 조각인지 알기 힘들다.

1. 이전에 '('를 만났다면 레이저가 될 것이고
2. ')'를 만났다면 쇠파이프의 끝이 될 것이다.

따라서 이를 해결하기 위해 다음과 같은 접근을 생각했다.

1. i번째 볼 때 i+1번째 까지 보기.
   • i번쨰와 i+1이 ()이 된다면 레이저이고 인덱스를 2만큼 증가시킨다.
   • 문제는 인덱스 에러를 신경써줘야 한다. 그러면 복잡해짐.
2. 이전에 '('를 만났는지 flag를 만들 것.
   • 위보다 코드가 훨씬 간결해진다. 각 (만났을 떄나 )만났을 떄 flag 잘 세워줄 것.
3. 처음 조작시 미리 ()를 레이저로 바꿔준다. (다른 사람 풀이 참조.)
   • 위보다 더욱 간결해진다. 또 파이썬에서 replace 메소드를 이용하면 간편해진다

구현

def solution(arrangement):
    stack = []
    answer = 0

    counts = 0
    flag = False #레이저 만났었는지에 대한 flag
    for token in arrangement:
        if token == '(':
            stack.append(token)
            flag = False
        else:
            stack.pop()
            if flag:
                answer += 1
            else:
                answer += len(stack)
            flag = True

    return answer

arrangement= "()(((()())(())()))(())"

print(solution(arrangement))

위처럼 stack에 '('를 넣어도 되지만 결국 관심사는 stack에 들어있는 '('의 갯수 이므로

stack에 남아있는 수만을 고려하여 아래와 같이 구현해도 된다.

def solution(arrangement):
    answer = 0

    bracketCounts = 0
    flag = False #레이저 만나서 pop했었니? 에 대한 플래그
    for token in arrangement:
        if token == '(':
            bracketCounts += 1
            flag = False
        else:
            bracketCounts -= 1
            if flag:
                answer += 1
            else:
                answer += bracketCounts
            flag = True

    return answer

arrangement= "(()(()))"

print(solution(arrangement))

얻을 점

마코프체인마냥 x를 볼 때 이전 시점을 고려해야 한다면 아예 바꿔주든가, 아니면 flag를 세워주자.