상세 컨텐츠

본문 제목

[programmers] 프로그래머스 괄호 변환(Python)

Problem Solving/programmers

by HelloMinchan 2020. 6. 19. 22:52

본문

(주)그렙

[programmers] 프로그래머스 괄호 변환

(Python)

(글쓴날 : 2020.06.19)

 


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

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


 

 

프로그래머스 괄호 변환


1) 문제

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

 

코딩테스트 연습 - 괄호 변환

카카오에 신입 개발자로 입사한 콘은 선배 개발자로부터 개발역량 강화를 위해 다른 개발자가 작성한 소스 코드를 분석하여 문제점을 발견하고 수정하라는 업무 과제를 받았습니다. 소스를 컴�

programmers.co.kr


2) 풀이 과정

* 시간 복잡도 : O(n)

 

소괄호들로 이루어진 문자열이 주어질 때, 올바른 괄호 문자열로 변환하는 문제입니다.

 

저의 경우, Python을 사용했습니다.

이 문제의 경우, 문제를 해결하는 로직이 서술되어 있기 때문에 해당 로직을 그대로 구현해 문제를 해결했습니다.

문자열 w를 u, v로 분리하는 함수와, 문자열 u가 올바른 괄호 문자열인지 확인하는 함수, 이 두 가지 함수만 따로 작성한 뒤, 문제에 서술되어 있는 로직을 그대로 구현하시면 됩니다.


3) 코드

 

* Python 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
# 문자열 w를 u, v로 분리하는 함수
def divide(w):
    openP = 0
    closeP = 0
    
    for i in range(len(w)):
        if w[i] == '(':
            openP += 1
        else:
            closeP += 1
        if openP == closeP:
            return w[:i + 1], w[i + 1:]
 
 
# 문자열 u가 올바른 괄호 문자열인지 확인하는 함수
def isBalanced(u):
    stack = []
    
    for p in u:
        if p == '(':
            stack.append(p)
        else:
            if not stack:
                return False
            stack.pop()
            
    return True
 
 
def solution(w):
    # 과정 1
    if not w:
        return ""
    
    # 과정 2
    u, v = divide(w)
    
    # 과정 3
    if isBalanced(u):
        # 과정 3-1
        return u + solution(v)
    # 과정 4
    else:
        # 과정 4-1
        answer = '('
        # 과정 4-2
        answer += solution(v)
        # 과정 4-3
        answer += ')'
        
        # 과정 4-4
        for p in u[1:len(u) - 1]:
            if p == '(':
                answer += ')'
            else:
                answer += '('
        
        # 과정 4-5
        return answer

 

관련글 더보기

댓글 영역