[파이썬python] 백준 10799번 - 쇠막대기

백준 10799번 쇠막대기 문제를 풀어보겠습니다.

제가 문제를 풀어가는 과정을 알려드릴테니 끝까지 집중해주세요!

https://www.acmicpc.net/problem/10799

10799번: 쇠막대기

문제요약)

쇠막대기와 레이저의 배치를 나타내는 괄호 표현이 주어졌을 때, 잘려진 쇠막대기 조각의 총 개수를 구하는 문제입니다. 

밑에 예시에선 답이 17개가 나와야겠죠?

사실 이 문제는 대표적인 스택을 이용하는 문제인데요!

백준에서 조금 고였다 하신분들이라면 괄호만 보고 얼핏 스택을 이용하는 문제라는 것을 눈치채실 수 있으실 겁니다!

하지만, 저는 고이다말았는지, 스택을 이용하는 건 알겠지만, 구현하는 게 많이 어렵더라고요..ㅠㅠ(아직은 수련이 더 필요해요..)

 

저는 손으로 직접 그려보면서 이해를 하려고 노력했습니다. 

끄적끄적

그러다가 레이저를 나타내는 '()'가 나올 때, '('의 수만큼 막대기가 잘려나간다는 것을 알게 되었어요. 

그리고 ')'가 나오면 막대기가 하나 더 생깁니다. 

그래서 핵심은 '('가 나오면 배열에 append하는 것과 '('다음에 바로 ')'가 나올 때를 알면 문제를 풀 수 있지 않을 까라고 생각했습니다. 

 

따라서 문제를 푸는 과정은 다음과 같을 거 같습니다. 

1. '('이 나오면 배열에 append합니다.

2. '()'이 나오면 배열에 있는 '('의 수만큼 정답을 count합니다. (이때도 배열 pop하나 해줘야됨)

3. ')'이 나오면 '('이 담긴 배열을 pop하고 정답에 1을 더합니다.

 

정답코드)

p = input()
arr = []
answer = 0
for i in range(len(p)):
    if p[i] == "(":
        arr.append("(")
    else:
        if p[i-1] == "(":
            arr.pop()
            answer+=len(arr)
        else:
            arr.pop()
            answer+=1
print(answer)

저는 2번을 구현하는 것이 좀 어려웠던거 같습니다. 

하지만, if-else문으로 '(' 일때와 ')'일때를 구분해서 처리를 해서 해결하였습니다. 

잇님들도 구현하는 것에 두려워하지 마시고 저처럼 차근차근 1,2,3 step을 쓰시고,

그대로 구현해보시면 좋을 거 같습니다..!

 

그럼 도움이 되셨다면 공감과 댓글 그리고 구독을 부탁드립니다.!!