https://programmers.co.kr/learn/courses/30/lessons/60058
코딩테스트 연습 - 괄호 변환
카카오에 신입 개발자로 입사한 콘은 선배 개발자로부터 개발역량 강화를 위해 다른 개발자가 작성한 소스 코드를 분석하여 문제점을 발견하고 수정하라는 업무 과제를 받았습니다. 소스를 컴
programmers.co.kr
문제 해결을 위한 과정
이 문제의 경우 재귀를 얼마나 잘 사용할 수 있느냐 그리고 구현 알고리즘을 얼마나 잘 사용할 수 있느냐가 중요한 문제였다고 생각합니다. 문제의 조건을 그대로 꼼꼼하게 코드로 옮기기만 한다면 쉽게 정답을 맞을 수 있는 문제였습니다.
먼저 재귀의 탈출 조건으로 빈 문자열이 들어온 경우 그대로 빈 문자열을 반환하는 것 과
문자열 W를 u, v로 분류하는 것입니다.
이 문제의 경우 균형 잡힌 괄호 문자열을 만드는 함수, 올바른 괄호 문자열인지 확인 하는 함수, solution함수 총 3개의 함수로 구분하여 코드를 작성하면 쉬운 문제였습니다.
균형 잡힌 괄호 문자열로 더이상 분류를 할 수 없게 최소한의 길이를 가진 u를 만들어 낼 수 있도록 균형잡인 괄호 문자열을 만드는 함수 balance함수에서 앞에서부터 몇번째 인덱스에서 최소한의 길이를 가진 균형잡인 괄호 문자열이 만들어지는지를 반환을 해주면 그 반환된 인덱스를 기준으로 리스트를 인덱싱 하여 u와 v를 구분할 수 있습니다.
그 후 u를 다시 올바른 괄호 문자열인지 확인하는 함수 correct를 통해 확인한 후 이 결과에 따라 문제의 조건처럼 재귀를 구현하면 되는 것입니다. 이후 과정은 문제를 소스코드로 그대로 옮기는 것이기 때문에 생략합니다.
소스코드
|
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
|
def balanced(p):
count = 0
for i in range(len(p)):
if p[i] == '(':
count += 1
elif p[i] == ')':
count -= 1
if count == 0:
return i
def correct(u):
count = 0
for i in range(len(u)):
if u[i] == '(':
count += 1
elif u[i] == ')':
count -= 1
if count < 0:
return False
return True
def solution(p):
if p == '':
return p
answer = ''
index = balanced(p)
u = p[:index + 1]
v = p[index + 1:]
if correct(u):
return (u + solution(v))
else:
answer += '('
answer += solution(v)
answer += ')'
u = list(u)
u = u[1:-1]
for i in range(len(u)):
if u[i] == '(':
u[i] = ')'
else:
u[i] = '('
answer += ''.join(u)
return answer
|
cs |
'알고리즘 > 프로그래머스' 카테고리의 다른 글
| 가사 검색 (Python) (0) | 2020.12.17 |
|---|---|
| 블록 이동하기 (Python) (0) | 2020.12.07 |
| 자물쇠와 열쇠 (Python) (0) | 2020.12.03 |
| 모의고사 (Level 1 Python) (0) | 2020.11.30 |
| 기둥과 보 설치 (Python) (0) | 2020.11.29 |