[Programmers] Iron bar.py (stack/queue)

#. Problem

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

* The copyright in this matter is in Programmers

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

    (a) 레이저는 여는 괄호와 닫는 괄호의 인접한 쌍 '()'으로 표현합니다. 또한 모든 '()'는 반드시 레이저를 표현합니다.

    (b) 쇠막대기의 왼쪽 끝은 여는 괄호 '('로, 오른쪽 끝은 닫힌 괄호 ')'로 표현됩니다.

  3. Create solution plan (select Algorithm, Data structure)

    - stack

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

  1. arrangement 요소를 하나씩 뽑아서,

     "(" 일 경우 stack에 쌓음

     ")"일 경우 stack에서 한 개의 "("을 빼내고 stack에 있는 "("의 개수만큼 count 해줌

     단, 이전에도 ")"였을 경우 막대기의 끝을 의미하므로 stack에서 한 개의 "("를 빼내고 +1을 count 해줌

     -> 여기서 이전 문자열이 무엇인지 저장해주는 변수가 필요

#. Code

def solution(arrangement):
    answer = 0
    stack = []
    for a in list(arrangement):
        if a == '(':
            stack.append(a)
            last = a
        else:
            stack.pop()
            if last == '(':
                answer += len(stack)
                last = a
            else:
                answer += 1
    return answer

  - (4~14) arrangement의 문자열을 하나씩 받는다

             만일, a가 '(' 일 경우 stack 에 쌓아주고 last 변수에 문자를 저장한다. (range 사용 시 이전 index(n-1)를 참조)

             그렇지 않을 경우(a가 ')'일 경우) stack에 있는 '(' 문자 하나를 빼준다. 

              - 여기서 last(이전 index)가 '('라면 레이져를 의미하므로 stack에 있는 '('의 개수만큼을 count해주고, 

                last가 ')' 라면 쇠막대기의 끝을 의미하므로 1만큼 count 해준다.

#. Other code

def solution(arrangement):
    answer = 0
    sticks = 0
    rasor_to_zero = arrangement.replace('()','0')
 
    for i in rasor_to_zero:
        if i == '(':
            sticks += 1
        elif i =='0' :
            answer += sticks
        else :
            sticks -= 1
            answer += 1
 
    return answer

  - 비슷하지만 더 간결하고 효율적인 코드.

    먼저 레이져를 0으로 치환해주면서 쇠막대만 신경쓰면 될 것 같다(last 변수는 필요 없게 되어버림)

    stack 대신 sticks 라는 정수형 변수를 사용하여 pop 함수가 필요 없게 되었다.