상세 컨텐츠

본문 제목

[programmers] 프로그래머스 쇠막대기(Python)

Problem Solving/programmers

by HelloMinchan 2020. 6. 16. 04:08

본문

(주)그렙

[programmers] 프로그래머스 쇠막대기

(Python)

(글쓴날 : 2020.06.16)

 


* programmers, 프로그래머스 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.


 

 

프로그래머스 쇠막대기


1) 문제

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

 

코딩테스트 연습 - 쇠막대기

여러 개의 쇠막대기를 레이저로 절단하려고 합니다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자릅니다. 쇠막대기와 레�

programmers.co.kr


2) 풀이 과정

* 시간 복잡도 : O(n)

 

소괄호들로 이루어진 배열이 주어질 때, 괄호를 구분하는 특정 규칙에 맞추어 쇠막대기의 수를 구하는 문제입니다.

 

저의 경우, 스택을 적용하였고, Python을 사용했습니다.

주어진 배열을 탐색하여, 여는 소괄호일 경우 스택에 저장하고, 닫는 소괄호일 경우 스택에서 한 개를 꺼낸 뒤, 이전에 탐색했던 소괄호에 따라 여는 소괄호일 시 레이저이므로 현재 쇠막대기의 개수인 스택의 길이만큼 답을 증가시키고, 닫는 소괄호일 시 쇠막대기의 끝이므로 답을 1 증가시켜 문제를 해결했습니다.


3) 코드

 

* Python 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def solution(arrangement):
    answer = 0
    
    stack = []
    for i in range(len(arrangement)):
        if arrangement[i] == '(':
            stack.append('(')
        else:
            stack.pop()
            
            if arrangement[i - 1== ')':
                answer += 1
            else:
                answer += len(stack)
                      
    return answer

 

관련글 더보기

댓글 영역