[Python] 10799: 쇠막대기

문제 링크

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

 

 

 

 

 

 

 

 

기본적인 아이디어는 다음과 같았다.

 

1. 열린 괄호 '('가 나오면 Stack에 push한다.

2. 닫힌 괄호 ')'가 나오면 Stack에 있던 '('를 pop한 뒤, 코드를 잘~ 짜서 개수를 세어준다.

 

다만 이렇게만 할 수 있다면 아마 9012번 괄호 문제와 다름 없었을 것이다. 고려해야 될 사항은 괄호가 나왔을 때 경우의 수가 2가지라는 것이다.

 

 

1. 해당 괄호가 레이저일 경우

  직전 문자가 열린 괄호, 그 다음 문자가 닫힌 괄호인 경우이다. 이 경우에는 일단 닫힌 괄호에 대응되는 열린 괄호를 Stack에서 pop해주고, 현재 Stack에 저장하고 있는 열린 괄호의 개수만큼 조각이 생긴다.  

2. 해당 괄호가 쇠막대기인 경우

  직전 문자가 닫힌 괄호, 그 다음 문자도 닫힌 괄호인 경우이다. 이 경우 쇠막대기가 끝났음을 의미하기 때문에 마지막 조각인 1만 더해주면 된다.

 

말로 설명하니 뭔가 난해한데, 출제자가 이해를 돕기 위해 친절하게 그림을 삽입해놨다. 확인해보자.

시작하자마자 레이저가 나오지만 Stack에 아무 것도 없기 때문에 0개가 추가된다.

그 다음 '('가 연달아 3개가 추가되고, (다음 문자가 ')'가 아니기 때문에 쇠막대기로 볼 수 있다.) 그 다음에는 레이저가 나오게 된다. 물론 3개의 쇠막대기를 자르면 6개가 되겠지만, 우선 그건 고려하지 않고 잘린 앞부분의 개수만 고려해보자. Stack에 존재하는 쇠막대기 '('가 3개기 때문에 현재까지 쇠막대기는 3개다. 이후 레이저가 또 나오기 때문에 6개가 된다.

그 다음 ')'가 선언되어 쇠막대기가 끝났음을 보여주는데, 이때는 여태까지 고려하지 않았던 뒷부분의 막대기 조각 1개만 더해주면 된다.

 

이 과정을 반복하면 0+3+3+1+3+1+2+1+1+1+1=17개가 나오는 걸 확인할 수 있다. 굿!

 

stack = []
cnt = 0
str = list(input().strip())
for i in range(len(str)):
    if str[i] == "(":       
        stack.append("(") # 스택에 추가 (쇠막대기의 시작 혹은 레이저의 시작)
    else:      
        stack.pop() # 열린 괄호를 스택에서 제거 (쇠막대기 끝 또는 레이저)
        if str[i-1] == "(": # 바로 직전 문자가 열린 괄호라면, 레이저인 경우
            cnt += len(stack) # 현재 스택의 길이만큼 쇠막대기가 잘리므로 더해줌
        else: # 바로 직전 문자가 닫힌 괄호라면, 쇠막대기가 끝나는 지점
            cnt += 1 # 쇠막대기의 끝 조각이므로 1을 더해줌

print(cnt)

 

* 원래는 코드를 짤 때 주석을 잘 안 다는  편인데, 다른 사람이 볼 때 주석의 유무가 얼마나 간절한지를 최근에 깨달았기 때문에 ... 조금이나마 이해가 쉽게 하기 위해서 주석을 열심히 달았다. 협업할 때는 습관으로 들일 필요가 있을 것 같다.

 

+) 링크 뒤에서 엔터 눌렀는데 왜 링크 박스 안 생기는지 알려주실 분 ...