두번의 시도 + 풀이과정참조를 했지만 제대로 이해하고 풀지 못했던 쇠막대기 문제에 대한 풀이를 해보겠다.
문제
위와 같이 여러개의 쇠막대기를 2차원공간에 수평으로 놔두고 레이저를 발사해서 쇠막대기를 자른다.
여기서 잘려진 쇠막대기의 갯수를 구한다.
예시
input : '()(((()())(())()))(())'
output : 17
풀이
문제를 보고 제일 처음에는 반복문을 돌려서 '('를 만나면 하나의 막대기가 추가되는 것으로 간주하고 '0'(레이저)를 만나면 추가된 쇠막대기의 배수가 증가하는 것으로 구정했다. 결론적으로 맞는 말이지만 stack을 사용하지 않는것이 문제였다.
민규님의 조언을 얻어 새로운 풀이를 짜보았다
def solution(argument):
[1] arguemnt = argument.replace('()', '0')
[2] count = 0
[3] stack = []
[4] end = ''
for i in range(len(arguemnt)):
[5] if arguemnt[i] == '(':
[6] stack.append(arguemnt[i])
[7] end += arguemnt[i]
[8] elif arguemnt[i] == '0':
[9] count += len(stack)
[10] end += arguemnt[i]
[11] elif end[-1] == '0' and arguemnt[i] == ')':
[12] stack.pop()
[13] count += 1
return count[1] 문자열에서 '('과 ')'이 연속되어 나오면 레이저이다. 따라서 '()'를 '0'으로 바꾸어 다른 쇠막대기의 시작점과 끝점을 구분하는데 차질이 없도록 한다
[2] 리턴값인 전체 쇠막대기의 갯수이다. 반목문을 돌려서 쇠막대기의 시작점을 만날 때 마다, 쇠막대기가 잘려서 생겨날 때 마다 하나씩 올라갈 것이다.
[3] 쇠막대기의 시작점을 담은 스텍 문자열이다. '('가 쇠막대기의 시작점이라면 ')'가 반드시 있어야 온전한 하나의 쇠막대기가 된다.
[4] 반복문을 돌리면서 현재 인덱스에 해당하는 문자열을 넣어준다. 반복문에서 지금 문자열이 쇠막대기의 끝인 ')'일 때 이전의 문자열이 무엇인지 알아야 한다.
[5] 반복문을 돌리고 문자가 '('일 때 쇠막대기가 하나 추가되는 것으로 간주한다. 따라서 stack에 값을 넣어주고[6] 어떤 값으로 이전문자열이 끝났는지[7] 나타내는 end에 지금 문자의 값을 넣어준다
[8] 지금의 문자열이 '0'(레이저)일 때 stack에 추가된 쇠막대기의 갯수를 count에 넣어준다[9]. 레이저를 만나기 전 쇠막대기는 stack에 추가만 될 뿐 count에는 들어가지 않는다. 마지막으로 지금의 문자열을 end변수에 넣어준다[10].
[11] 만약 이전의 문자열이 '0'(레이저)일 때 쇠막대기가 닫힌 상태 ')'를 확인 해 주어야한다. 그래서 지금의 문자열에서 쇠막대기가 ')'로 닫히면 stack에서 추가된 쇠막대기의 시작 '('를 pop명령어를 통해서 제일 마지막에 추가된 것부터 제거한다[12]. 스텍에서 제거된 쇠막대기(탐색으로 하나의 쇠막대기로 인정된)를 count에 넣어준다
