코딩테스트 연습> 스택/큐> 쇠막대기

 

<문제링크: https://programmers.co.kr/learn/courses/30/lessons/42585>

 

문제설명: 여는 괄호와 닫는 괄호로 이루어진 문자열이 주어지고, 여는 괄호 '('가 나올 때마다 막대기가 생성된다. 중간에 괄호과 완성되면, 즉 '()'이 만나게되면 레이저를 발사해 현재까지 생성된 막대기를 두 동강낸다. 이렇게 했을 때 누적된 막대기가 잘려나간 조각들의 총 합을 구하면 된다.

 

[1차 시도]

def solution(arrangement):
    ans = 0     ## 조각 개수
    temp = 1    ## 막대기 개수
    for a in range(1,len(arrangement)):
        if arrangement[a] == '(':
            temp+=1
        else:
            if arrangement[a-1]=='(':
                temp-=1
                ans+=temp
            else:    ## '))'
                temp-=1
                ans+=1
    return ans

 

풀이: 먼저 막대기의 조각들 수를 더해줄 최종 합 ans와 중간에 생성되는 막대기 개수를 누적할 temp 변수를 만들어 준다. 뒤에서 for문으로 문자열을 돌면서 '('가 나오면 막대기가 생성된다는 의미이므로 temp+1을 해주는데, 문제에서 문자열의 시작은 항상 '('이라고 주어졌으므로, temp의 처음 시작을 1로 초기화 해준다.

 

arrangement를 for문으로 돌면서 탐색하는데, 이때 for문의 범위는 현재 위치의 앞 문자와 비교하기 위해 1부터 시작한다. 만약 현재 여는 괄호 '('가 나오면, 막대 개수 temp에 +1씩 더해준다. 

 

만약 닫는 괄호 ')'가 나오면, 이는 또 2가지 경우로 볼 수 있는데:

 

1. 앞의 문자가 '('일 때, 즉 괄호가 '()'로 완성이 됐으므로 레이저를 발사해야 하고 이는 곧 현재까지 누적 된 막대기의 개수 만큼 잘라주고 자른 기준의 왼쪽 조각들을 처리해주어야 한다. 따라서 현재 temp에서 바로 직전의 '('는 레이저를 만들기 위한 것으로 고려하지 않아도 되기 때문에 -1을 해주고 남은 막대기 개수만큼 ans에 누적해준다.

 

2. 앞의 문자가 ')'일때는 닫는 괄호가 연속 2번 '))' 이므로 막대기의 수명이 다했다고 볼 수 있다. 그러면 temp에서 막대기 개수를 1개 빼주고 또한 현재 ans에는 레이저 발사 기준 앞의 조각들만 더해줬으므로, 레이저 발사 후 남은 조각 1개를 ans에 더해줌으로써 막대기 조각들을 깔끔히 처리하고 다음으로 넘어갈 수 있다.

 

최종적으로 ans를 return하면, 

 

 

채첨결과: 테스트케이스 20개가 모두 잘 통과한다. 

 

 

 

제출 후에 다른사람들 풀이를 보면서 다른 방법으로도 풀어봤다.

 

[2차 시도]

def solution(arrangement):
    ans = 0
    temp = 0
    transform = arrangement.replace('()','0')
    for t in transform:
        if t=='(':
            temp+=1
        elif t==')':
        	temp-=1
            ans+=1
        else:
            ans+=temp
    return ans

 

풀이: 어차피 괄호가 완성되는 시점에 레이저 점을 생성하므로, '()'를 한개의 string으로 묶어서 0으로 바꿔주는 방법이다. 이렇게 원 문자열을 변형시킨 것을 새로운 문자열 transform에 저장하고, transform에서 for문을 돌린다.

 

만약에 현재 t가 여는 괄호 '(' 라면, 막대기의 개수를 저장하는 임시 변수 temp에 +1해주고, 닫는괄호라면 ')' 바로 앞에서 더해줬던 1만큼 다시 빼고, 현재까지의 막대기 개수를 최종 답 ans에 더해준다.

 

그리고 만약 괄호가 아닌 0이라면, 레이저로 현재까지 저장한 개수의 막대기를 잘라야하므로 ans에 temp 수 만큼 더해주고 최종적으로 ans를 return한다.

 

채첨결과: 모두 잘 통과하고 소요시간이 절반정도 줄어든 것 같다.