[프로그래머스] 코딩테스트 고득점 Kit > 쇠막대기

# 문제

# 문제 접근

문제만 봤을 때 굉장히 복잡할 것 같다고 느낀 문제였다.

우선 괄호로 이루어진 입력이 보기가 쉽지 않았다. 중요한 것은 "()" 모양으로 된 것은 레이저 라는 것이다.

그래서 ()를 레이저(R)로 표시한 후 생각하였다.

예시의 입력은 R(((RR)(R)R))(R) 로 바뀌게 된다.

막대기가 하나 완성이 되기 위해선 "(" 과 ")" 가 필요하다. 괄호 쌍을 맞추는 알고리즘 문제를 풀어 본 적이 있는가? 이와 유사하다.

스택에 "("를 만나면 쌓고, ")"를 만나면 스택으로 부터 pop 하여 쌍을 맞추게 되는 것이다.

그럼 R을 만났을 땐 어떻게 할 것인가?

"("가 스택에 쌓였다는 것은 막대기가 하나 생성되었다는 것을 의미한다.

"("가 N개 스택에 쌓였다는 것은 막대기가 N개 생성되었다는 것을 의미한다.

"("가 N개 쌓였을 때 그 사이에 레이저(R)가 존재한다면, 레이저를 기준으로 막대기들의 왼쪽 부분은 잘려나가게 되고 이 때 생성되는 갯수는 N개가 된다.

즉, (((R 일 때, 막대기는 3개가 생성이 된다는 것이다.

이번엔 ")"를 만났다고 생각해보자. 그럼 스택에 "("를 하나 pop 하고, 막대기가 하나 생성 될 것이다. 이게 끝이다.

즉, (((RR) 일 때, (((RR에 의해 6개의 막대기가 잘려나가 생성되고 )에 의해 잘리고 남은 부위와 합쳐져 하나의 막대기 쌍이 생긴 것이다. 

# 문제 풀이

1. ()를 "R" 로 치환한다. (하지 않아도 상관 없으나 처리가 귀찮다.)

2. 처음부터 끝까지 루프를 돈다.

3-1. "("를 만나면 스택에 쌓는다.

3-2.  "R"을 만나면 지금까지 스택에 쌓인 "("의 개수만큼 막대기의 수를 증가시킨다.

3-3. ")"를 만나면 막대기의 수를 하나 증가시키고 스택에서 pop 한다.

4. 개수를 반환한다.

# 코드 작성

def solution(arrangement):
    answer = 0
    # () 를 R로 바꾼다.
    replaced_arrangement = arrangement.replace("()", "R")
    stack = []
    
    for item in replaced_arrangement:
        # "("를 만나면 스택에 쌓는다.
        if item == "(": 
            stack.append(item)
            
        # "R"을 만나면 스택의 길이만큼 막대기의 수를 증가시킨다.
        elif item == "R" :
            answer += len(stack)
            
        # ")"를 만나면 막대기의 수를 1 증가시키고 스택에서 pop한다.
        elif item == ")" :
            answer += 1
            stack.pop()
            
    # 결과를 반환한다.
    return answer

 

 * 본 문제의 출처는 프로그래머스(https://programmers.co.kr/) 입니다. 문제가 될 시 삭제하겠습니다.