괄호 변환

https://school.programmers.co.kr/learn/courses/30/lessons/60058

프로그래머스

---

try 1

1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다. 
2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다. 
3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다. 
  3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다. 
4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다. 
  4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다. 
  4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다. 
  4-3. ')'를 다시 붙입니다. 
  4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다. 
  4-5. 생성된 문자열을 반환합니다.

처음에는 문제에서 제시한 알고리즘 뒷부분이 한번에 이해가 안됐다.

그래서 1.부터 하나씩 구현했더니 이해가 됐다.

그리고나선 하나씩 구현한 것을 합쳤다.

 

※ 나의 코드

#나의 코드

def solution(p):
    answer = ''
    if p == '':
        return ''
  
    for length in range(2,len(p)+1,2):
        u = p[:length]
        if u.count('(') == u.count(')'):
            v = p[length:]
            break

    import re
    f = re.compile('\).*\(')
    if f.match(u):
        gen = '(' + solution(v) + ')' + u[1:-1].replace('(','*').replace(')','(').replace('*',')')
        answer += gen
    else:
        answer += u + solution(v)
    
    return answer

문제 풀이)

p가 ''이면 ''을리턴하도록 if문 구성

for문을 진행 할 수 록 p를 2의 배수로 잘라서 u에 넣은 다음 u가 균형잡힌 괄호 문자열이라면 나머지 길이는 v에 넣고 for문 중지

정규식을 이용하여 u가 올바른 괄호 문자열인지 아닌지 확인한 후 제시된 알고리즘대로 if문 구성

 

테스트 결과 - 총합 6.82ms

 

테스트 1 〉	통과 (0.10ms, 10.2MB)
테스트 2 〉	통과 (0.07ms, 10.2MB)
테스트 3 〉	통과 (0.09ms, 10MB)
테스트 4 〉	통과 (0.11ms, 10.2MB)
테스트 5 〉	통과 (0.10ms, 9.96MB)
테스트 6 〉	통과 (0.07ms, 10.3MB)
테스트 7 〉	통과 (0.08ms, 10.3MB)
테스트 8 〉	통과 (0.11ms, 10.2MB)
테스트 9 〉	통과 (0.08ms, 10.2MB)
테스트 10 〉	통과 (0.10ms, 10.2MB)
테스트 11 〉	통과 (0.15ms, 10.3MB)
테스트 12 〉	통과 (0.14ms, 10.1MB)
테스트 13 〉	통과 (0.11ms, 9.97MB)
테스트 14 〉	통과 (0.22ms, 10.2MB)
테스트 15 〉	통과 (0.17ms, 10.3MB)
테스트 16 〉	통과 (0.40ms, 10.2MB)
테스트 17 〉	통과 (0.46ms, 10.3MB)
테스트 18 〉	통과 (0.60ms, 10.3MB)
테스트 19 〉	통과 (0.74ms, 10MB)
테스트 20 〉	통과 (0.46ms, 10.2MB)
테스트 21 〉	통과 (0.85ms, 10.2MB)
테스트 22 〉	통과 (0.37ms, 10.2MB)
테스트 23 〉	통과 (0.53ms, 10.2MB)
테스트 24 〉	통과 (0.35ms, 10.2MB)
테스트 25 〉	통과 (0.36ms, 10.3MB)

---

※ 더 좋은 다른 사람 코드

# 다른 사람 코드

def solution(p):
    if p=='': return p
    r=True; c=0
    for i in range(len(p)):
        if p[i]=='(': c-=1
        else: c+=1
        if c>0: r=False
        if c==0:
            if r:
                return p[:i+1]+solution(p[i+1:])
            else:
                return '('+solution(p[i+1:])+')'+''.join(list(map(lambda x:'(' if x==')' else ')',p[1:i]) ))

다른 사람 코드 해석)

6.82 -> 2.57

약 4.25ms(약 60퍼) 줄음 (약 2.5배 빠름)

 

저의 코드와 다른 점만 해석

 

다른 사람 코드는 p가 올바른 괄호 문자열인지 확인하는 r 변수과 r 변수가 판단하기 위해 필요한 c변수를 만듦

맨 처음에 '('로 시작한다면 올바른 괄호 문자열 -> c = -1 -> r = True -> 이후에 c가 0이 되면 값이 리턴이 되기 때문에 c는 양수가 나올 수 없기 때문에 r은 True만 나옴

맨 처음에 ')'로 시작한다면 올바른 괄호 문자열이 아님 -> c = 1 -> r = False

이부분이 테스트 시간에 가장 큰 영향을 준 것 같음

 

코드 마지막에  join(list(map(lambda x)))가 제가 짠 replace보다 더 빠름

이부분만 바꾸었더니 테스트 시간 총합이 약 20퍼 줄었음

 

테스트 결과 - 총합 2.57ms

테스트 1 〉	통과 (0.01ms, 10.2MB)
테스트 2 〉	통과 (0.01ms, 10.3MB)
테스트 3 〉	통과 (0.01ms, 10.2MB)
테스트 4 〉	통과 (0.01ms, 10.1MB)
테스트 5 〉	통과 (0.01ms, 10.4MB)
테스트 6 〉	통과 (0.01ms, 10.3MB)
테스트 7 〉	통과 (0.01ms, 10.1MB)
테스트 8 〉	통과 (0.01ms, 10.1MB)
테스트 9 〉	통과 (0.02ms, 10.1MB)
테스트 10 〉	통과 (0.02ms, 10.2MB)
테스트 11 〉	통과 (0.03ms, 10.1MB)
테스트 12 〉	통과 (0.03ms, 10.2MB)
테스트 13 〉	통과 (0.06ms, 10.3MB)
테스트 14 〉	통과 (0.08ms, 10.3MB)
테스트 15 〉	통과 (0.10ms, 10.2MB)
테스트 16 〉	통과 (0.22ms, 10.3MB)
테스트 17 〉	통과 (0.12ms, 10.1MB)
테스트 18 〉	통과 (0.31ms, 10.2MB)
테스트 19 〉	통과 (0.27ms, 10.4MB)
테스트 20 〉	통과 (0.36ms, 10.2MB)
테스트 21 〉	통과 (0.20ms, 10.3MB)
테스트 22 〉	통과 (0.24ms, 10.2MB)
테스트 23 〉	통과 (0.27ms, 10.1MB)
테스트 24 〉	통과 (0.06ms, 10.3MB)
테스트 25 〉	통과 (0.10ms, 10.2MB)