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

문제 : https://programmers.co.kr/learn/courses/30/lessons/42585

코딩테스트 연습 - 쇠막대기 | 프로그래머스

이 문제는 백준에도 있고 여기저기 다있다. 기본적으로 괄호를 다루는 문제는 스택/큐 분야에서도 나오고 (특히 학부생때 배우는 계산기 만드는 알고리즘이나 prefix-postfix 바꾸기 등) 그래서 좀 봐두려고 한다.

 

근데 이 문제는 꽤 간단한편이다. 문제를 설명하자면

• (====공간====) -> 쇠막대기
• () -> 레이저

이 상황에서 레이저로 잘린 총 쇠막대기의 갯수를 구하는 문제다.

솔직히 처음 딱 보고 못풀음...취준맨 알고리즘 풀이 능력 무엇.

 

해결방법:

1. 처음부터 쭉 읽는다
   1. "(" 이 한번 나오면 일단 num_stick (막대기 갯수) +1 해줌
   2. 다음 사람을 위해 tmp_before 에다 "(" 저장, 이건
      1. arr[i], arr[i-1] 보기 싫어서 index단위 iteration 을 잘 안쓰기 때문에 나는 저번 state를 저장하는 편이다.
   3. 보다가 ")"이 나오면
      1. 바로 저번 문자가 "(" 인 경우는  () 니까 레이저
         1. 그러면 우선 막대기 갯수 더한거 했으니까 (1-1) 우선 num_stick -=1 하고
         2. 이제까지 나온 막대기 갯수 만큼 잘려서 나오니까 answer에 num_stick 을 더해주고
         3. 저번 state ")"로 저장
      2.  저번 문자가 ")" 인 경우는 그냥 막대기 끝부분이 하나 더 나온거다. num_stick -1 해주고 answer +1 

아마 O(N) 일듯 for loop 한번돌고 loop안에는 if-else 뿐이니까.

그리고  "    d = [c for c in arrangement] "  이 코드는 그냥 arr[i] 쓰기 싫어서 나온 방식이다. 

 

def solution(arrangement):
    answer = 0
    num_stick = 0

    d = [c for c in arrangement]
    tmp_before = d[0]
    for c in d:
        if c == "(":
            num_stick+=1
            tmp_before = "("
        else:
            if tmp_before=="(":
                num_stick-=1
                answer+=num_stick
                tmp_before = ")"
            else:
                num_stick-=1
                answer+=1

            


    return answer