프로그래머스 문제 풀이 쇠막대기

문제 URL 쇠막대기

Contents

1. 문제 지문 파악하기
2. 구르미의 알고리즘 풀이

문제 지문 파악하기

이번에도, 입력을 통해서 문제를 파악해보도록 하겠습니다. 문제의 입력은 이렇습니다.

 

입력:
arrangement = "()(((()())(())()))(())"

 

보기 쉽게 "()" 즉 막대가 잘린 곳을 나눠보도록 하겠습니다.

 

"() ((( () () )( () ) () ))( () )"

 

가장 왼쪽의 경우는 접점이 없습니다. "()" 이것은 단순이 잘리는 지점을 의미하기 때문이지요. 또한, 완전히 괄호가 닫힌 경우, 아예 다른 부분이라고 생각해도 무방합니다. 즉 이렇게 생각해도 무방합니다.

 

"((( () () )( () ) () ))" + "( () )"

 

먼저 두번째 부분부터 살펴봅시다.

 

"( () )"
1 () 1

 

이 경우는 1개의 막대가 2개로 잘리게 됩니다. 이제 첫 번째를 살펴봅시다.

 

"((( () () )( () ) () ))"

 

이 부분에서, 막대의 개수로 보면 이렇게 나뉘게 됩니다.

 

"3 () 3 () 4 () 3 () 2"

 

이렇게 해서 15개의 막대가 생깁니다. 이제 개수들을 더하면 되죠. 즉 답은 15 + 2 = 17. 17개입니다. 이렇게 사람의 눈으로 답을 찾아내긴 쉽지만, 어떻게 프로그래밍으로 나타낼 수 있을까요? 이런 문제는 대개 "스택"으로 풀 수 있습니다.

저의 문제 풀이 방식은 다음과 같습니다.

 

"("이 나오면, 스택에 넣고 ")"이 나오면 스택에서 빼고 스택 길이를 더해주자!

 

과연 이게 맞는지 살펴보겠습니다. arrangement를 순회해보도록 하죠.

 

arrangement = "()(((()())(())()))(())"
st = []

 

첫 번째 문자는 "("입니다. 스택에 넣죠

 

idx = 0
arrangement = "'(' )(((()())(())()))(())"
st = ["("]

 

두 번째 문자는 ")"입니다. 스택에서 문자를 뺀 후, 스택의 길이를 더해보겠습니다.

 

idx = 1
arrangement = "( ')' (((()())(())()))(())"
st = [] // ")"이 나와서 "(" 하나가 빠짐.
answer = 0 // st길이는 0이니까 더해도 달라지지 않음.

 

계속 진행해보도록 하겠습니다.

 

idx = 2
arrangement = "() '(' ((()())(())()))(())"
st = ["("] 
answer = 0

idx = 3
arrangement = "()( '(' (()())(())()))(())"
st = ["(", "("]
answer = 0 

idx = 4
arrangement = "()(( '(' ()())(())()))(())"
st = ["(", "(", "("] 
answer = 0 

idx = 5
arrangement = "()((( '(' )())(())()))(())"
st = ["(", "(", "(", "("] 
answer = 0 

idx = 6
arrangement = "()(((( ')' ())(())()))(())"
st = ["(", "(", "("]  // ")"이 나와서 "(" 하나가 빠짐.
answer = 3 // st의 길이는 3이다

idx = 7
arrangement = "()(((() '(' ))(())()))(())"
st = ["(", "(", "(", "("] 
answer = 3

idx = 8
arrangement = "()(((()( ')' )(())()))(())"
st = ["(", "(", "("]  // ")"이 나와서 "(" 하나가 빠짐.
answer = 6 // st의 길이는 3이다

idx = 9
arrangement = "()(((()() ')' (())()))(())"
st = ["(", "("] // ")"이 나와서 "(" 하나가 빠짐.
answer = 8 // st길이는 2이다.

idx = 10
arrangement = "()(((()()) '(' ())()))(())"
st = ["(", "(", "("] 
answer = 8 

idx = 11
arrangement = "()(((()())( '(' ))()))(())"
st = ["(", "(", "(", "("] 
answer = 8 

idx = 12
arrangement = "()(((()())(( ')' )()))(())"
st = ["(", "(", "(",] // ")"이 나와서 "(" 하나가 빠짐.
answer = 11 // st의 길이는 3이다.

idx = 13
arrangement = "()(((()())(() ')' ()))(())"
st = ["(", "("] // ")"이 나와서 "(" 하나가 빠짐.
answer = 13 // st의 길이는 2이다.

idx = 14
arrangement = "()(((()())(()) '(' )))(())"
st = ["(", "(", "("] 
answer = 13 

idx = 15
arrangement = "()(((()())(())( ')' ))(())"
st = ["(", "("] // ")"이 나와서 "(" 하나가 빠짐.
answer = 15 // st의 길이는 2이다.

idx = 16
arrangement = "()(((()())(())() ')' )(())"
st = ["("] // ")"이 나와서 "(" 하나가 빠짐.
answer = 16 // st의 길이는 1이다.

idx = 17
arrangement = "()(((()())(())()) ')' (())"
st = [] // ")"이 나와서 "(" 하나가 빠짐.
answer = 16 // st의 길이는 0이다.

idx = 18
arrangement = "()(((()())(())())) '(' ())"
st = ["("] 
answer = 16

idx = 19
arrangement = "()(((()())(())()))( '(' ))"
st = ["(", "("] 
answer = 16

idx = 20
arrangement = "()(((()())(())()))(( ')' )"
st = ["("] // ")"이 나와서 "(" 하나가 빠짐.
answer = 17 //st의 길이는 1이다.

idx = 21
arrangement = "()(((()())(())()))(() ')'"
st = [] // ")"이 나와서 "(" 하나가 빠짐.
answer = 17 //st의 길이는 0이다.

 

오, 해결되었습니다. 근데 실제 코드를 제출하면, 모두 실패처리가 됩니다. 왜 그럴까요? 여기서 한 가지 예외상황을 안 처리했기 때문입니다. 입력을 한 번 바꿔볼까요?

 

입력 :
arrangement = "(())"

 

이것은 2개의 막대로 나뉘는 입력입니다. 근데 제가 세운 알고리즘을 한 번 적용시켜보죠.

 

idx = 0
arrangement = "'(' ())"
st = ["("]
answer = 0

idx = 1
arrangement = "( '(' ))"
st = ["(", "("]
answer = 0

idx = 2
arrangement = "(( ')' )"
st = ["("] // ")"이 나와서 "(" 하나가 빠짐.
answer = 1 // st 길이는 1이다.

idx = 3
arrangement = "(() ')'"
st = [] // ")"이 나와서 "(" 하나가 빠짐.
answer = 1 // st 길이는 0이다.

 

어떻게 하면 좋을까요? 입력과 그림을 잘 보면, ")" 이전에, "("가 나오면, 막대의 개수가 스택의 길이만큼, 그렇지 않으면, 1개씩 더해지는 것을 알 수 있습니다. 즉, idx = 3 일 때, 이전 idx=2 문자열이 '('이 아닌 이 상황에서 1을 더해주는 것으로 하면 됩니다.

 

idx = 3
arrangement = "(() ')'"
st = [] // ")"이 나와서 "(" 하나가 빠짐.
answer = 2 // idx = 2 ")"이라서, ("("가 아니라서) 1을 더해준다.

 

이 공식이 맞는지 첫 번째 입력에서도 한 번 적용시켜보도록 하겠습니다.

 

idx = 0
arrangement = "'(' )(((()())(())()))(())"
st = ["("]
answer = 0

idx = 1
arrangement = "( ')' (((()())(())()))(())"
st = [] // ")"이 나와서 "(" 하나가 빠짐.
answer = 0 // 이전 문자는 "("이니까 스택의 길이를 더해준다.

idx = 2
arrangement = "() '(' ((()())(())()))(())"
st = ["("]
answer = 0

idx = 3
arrangement = "()( '(' (()())(())()))(())"
st = ["(", "("]
answer = 0

idx = 4
arrangement = "()(( '(' ()())(())()))(())"
st = ["(", "(", "("]
answer = 0

idx = 5
arrangement = "()((( '(' )())(())()))(())"
st = ["(", "(", "(", "("]
answer = 0

idx = 6
arrangement = "()(((( ')' ())(())()))(())"
st = ["(", "(", "("] // ")"이 나와서 "(" 하나가 빠짐.
answer = 3 // 이전 문자는 "("이니까 스택의 길이를 더해준다. st의 길이는 3이다.

idx = 7
arrangement = "()(((() '(' ))(())()))(())"
st = ["(", "(", "(", "("]
answer = 3

idx = 8
arrangement = "()(((()( ')' )(())()))(())"
st = ["(", "(", "("] // ")"이 나와서 "(" 하나가 빠짐.
answer = 6 // 이전 문자는 "("이니까 스택의 길이를 더해준다. st의 길이는 3이다.

idx = 9
arrangement = "()(((()() ')' (())()))(())"
st = ["(", "("] // ")"이 나와서 "(" 하나가 빠짐.
answer = 7 // 이전 문자는 "("가 아니다. 즉 1을 더해준다.

idx = 10
arrangement = "()(((()()) '(' ())()))(())"
st = ["(", "(", "("]
answer = 7

idx = 11
arrangement = "()(((()())( '(' ))()))(())"
st = ["(", "(", "(", "("]
answer = 7

idx = 12
arrangement = "()(((()())(( ')' )()))(())"
st = ["(", "(", "(",] // ")"이 나와서 "(" 하나가 빠짐.
answer = 10 // 이전 문자는 "("이니까 스택의 길이를 더해준다. st의 길이는 3이다.

idx = 13
arrangement = "()(((()())(() ')' ()))(())"
st = ["(", "("] // ")"이 나와서 "(" 하나가 빠짐.
answer = 11 // 이전 문자는 "("가 아니다. 즉 1을 더해준다.

idx = 14
arrangement = "()(((()())(()) '(' )))(())"
st = ["(", "(", "("]
answer = 11

idx = 15
arrangement = "()(((()())(())( ')' ))(())"
st = ["(", "("] // ")"이 나와서 "(" 하나가 빠짐.
answer = 13 // 이전 문자는 "("이니까 스택의 길이를 더해준다. st의 길이는 2이다.

idx = 16
arrangement = "()(((()())(())() ')' )(())"
st = ["("] // ")"이 나와서 "(" 하나가 빠짐.
answer = 14 // 이전 문자는 "("가 아니다. 즉 1을 더해준다.

idx = 17
arrangement = "()(((()())(())()) ')' (())"
st = [] // ")"이 나와서 "(" 하나가 빠짐.
answer = 15 // 이전 문자는 "("가 아니다. 즉 1을 더해준다.

idx = 18
arrangement = "()(((()())(())())) '(' ())"
st = ["("]
answer = 15

idx = 19
arrangement = "()(((()())(())()))( '(' ))"
st = ["(", "("]
answer = 15

idx = 20
arrangement = "()(((()())(())()))(( ')' )"
st = ["("] // ")"이 나와서 "(" 하나가 빠짐.
answer = 16 // 이전 문자는 "("이니까 스택의 길이를 더해준다. st의 길이는 1이다.

idx = 21
arrangement = "()(((()())(())()))(() ')'"
st = [] // ")"이 나와서 "(" 하나가 빠짐.
answer = 17 // 이전 문자는 "("가 아니다. 즉 1을 더해준다.

 

오 정확하게 되는군요! 바로 코드로 바꿔봅시다.

구르미의 알고리즘 풀이

이전 절 "문제 지문 파악하기"를 토대로 세운 알고리즘을 순서대로 나열하면 다음과 같습니다.

1. 스택을 생성합니다.
2. arragement를 길이만큼 순회합니다.
   1. 현재 문자가 '('인지 체크합니다.
      1. 맞다면, 스택에 저장합니다.
      2. 아니라면 다음을 실행합니다.
         1. 스택에서 데이터를 하나 뻅니다.
         2. 만약 문자열에서 현재 문자의 이전 문자가 '('라면, 스택 길이를 아니라면 1을 answer에 더해줍니다.
3. answer를 반환합니다.

이를 코드로 표현하면 다음과 같습니다.

 

PYTHON 코드

def solution(arrangement):
    # 1. 스택 생성
    st = []
    answer = 0
    
    # 2. arrangement를 순회합니다.
    for (i, e) in enumerate(arrangement):
        # 1. "(" 인지 체크합니다.
        # 1-1. "(" 라면, 스택에 넣습니다.
        if e == "(":
            st.append(e)
        # 1-2
        # 1-2-1. 스택에서 꺼냅니다.
        # 1-2-2. 이전 문자열이 "("이면, 스택 길이를, 아니라면 1을 answer에 더합니다.
        else:
            st.pop()
            answer += len(st) if arrangement[i-1] == "(" else 1
        
    return answer

 

이번엔 CPP 코드입니다. 언어만 바뀐 것이지 알고리즘은 같습니다.

 

CPP 코드

#include <string>
#include <vector>
#include <stack>

using namespace std;

int solution(string arrangement) {
    stack<char> st;
    int answer = 0;
    int idx = 0;
    
    for (const auto & elem : arrangement) {
        if (elem == '(') {
            st.push(elem);
        } else {
            st.pop();
            answer += (arrangement[idx-1] == '(') ? st.size() : 1;    
        }
        
        idx += 1;
    }
    
    return answer;
}