[프로그래머스] 스택/큐 - 쇠막대기 (python)

스택/큐 - 쇠막대기, 문제 확인

처음보는 신기한 유형의 문제이다. 문제 설명은 아래와 같다.

 

---

쇠막대기를 아래에서 위로 겹쳐놓고 레이저를 위에서 수직으로 발사해 쇠막대기를 자르려 함

짧은 쇠막대기가 긴 쇠막대기 위에 오도록 배치

각 쇠막대기를 자르는 레이저는 적어도 하나 존재

 

레이저는 어떤 쇠막대기의 양끝점과도 겹치지 않음

레이저는 ()로 표현함

쇠막대기의 왼쪽 끝은 (로, 오른쪽 끝은 )로 표현 

 

 

쇠막대기, 레이저의 배치를 표현한 문자열 arrangement가 주어질 때,

잘린 쇠막대기 조각의 총 개수를 return

 

 

스택/큐 - 쇠막대기, 문제 풀이

먼저 레이저 ()를 전부 *값으로 변경해주었다.

 

def solution(arrangement):
    answer = 0
    arrangement = arrangement.replace("()","*")

 

 

그다음 어떻게 할지 생각을 해보다가 스택/큐 문제인 만큼 스택/큐를 사용해서 풀려고 했는데 도저히 떠오르지 않아서 일단 다음 방법을 쓰기로 했다.

 

먼저 "(" 와 ")" 를 각각 찾아 인덱스를 저장하고 "(" ~ ")" 사이에 있는 "*" 개수를 구한 후 +1 해준 값을 계속 더해주는 것이다. 그리고 그 다음 "(" 와 ")" 를 찾을 때는 이전 인덱스 다음부터 찾아주면 된다. +1을 해주는 이유는 쇠막대기 하나에 레이저가 2개 지나가면 3조각이 되기 때문이다.

 

    for i in range(arrangement.count("(")):
        index_l=arrangement.find("(",index_l+1)
        index_r=arrangement.find(")",index_r+1) 
        tmp=arrangement[index_l:index_r].count("*")
        answer+=tmp+1

 

 

그럼 예시로 주어진 arrangement일 때, 인덱스 1~6 사이에 *이 2개, 2~9 사이에 *이 3개, 3~11 사이에 *이 4개, 7~12 사이에 *이 2개, 13~15 사이에 *이 1개이므로 3+4+5+3+2=17이 된다.

 

 

 

전체 코드는 아래와 같다.

 

def solution(arrangement):
    answer = 0
    arrangement = arrangement.replace("()","*")
    index_r=-1; index_l=-1
    
    for i in range(arrangement.count("(")):
        index_l=arrangement.find("(",index_l+1)
        index_r=arrangement.find(")",index_r+1) 
        tmp=arrangement[index_l:index_r].count("*")
        answer+=tmp+1

    return answer

 

 

아래와 같이 전체 테스트케이스를 통과할 수 있다.