카카오 블라인드 채용

[카카오] 2020 KAKAO BLIND RECRUITMENT 1차 풀이 – 괄호 변환

이 포스팅에서는 2020 카카오 블라인드 채용 1차 문제인 ‘괄호 변환’ 문제를 해설합니다. 본 풀이에 대한 테스트는 https://programmers.co.kr/learn/courses/30/lessons/60058에서 수행하였으며 공식 풀이와 일치하지 않을 수 있습니다.

공식 풀이는 링크를 참조하시기 바랍니다.


괄호 변환

출처 : 2020 KAKAO 블라인드 채용 온라인 1차
링크 : https://programmers.co.kr/learn/courses/30/lessons/60058
카테고리 : 재귀 호출
난이도 : 쉬움


문제 요약

주어진 괄호 문자열을 올바른 괄호 문자열로 바꾸어 출력. 그 방법은 문제 설명에 같이 주어진다.

  1. 문자열이 빈 문자열이면 즉시 빈 문자열을 리턴한다.
  2. 최초의 ‘균형 잡힌 문자열’ (열기 괄호와 닫기 괄호의 수가 똑같음)을 찾아서 u에 저장하고, 나머지는 v에 저장한다.
  3. u가 ‘올바른 문자열’ (왼쪽부터 열기와 닫기 괄호를 셀 때 어떤 순간에도 닫기 괄호의 수가 열기 괄호의 수보다 많지 않은 문자열)이면 u는 그대로 두고 v에 대해 맨 처음부터 알고리즘을 수행한 결과를 계산해 u + v를 반환.
  4. u가 ‘올바르지 않은 문자열’이면 아래와 같은 작업을 반복한다.
    1. u의 가장 앞 뒤 문자열을 제거하고, 나머지 문자열에 대해 열기 괄호는 닫기 괄호로, 닫기 괄호는 열기 괄호로 바꾼다.
    2. v에 대해 알고리즘을 1번부터 다시 수행한다. process(v)
    3. “(” + process(v) + “)” + u를 리턴한다.

문제 풀이

주어진대로 코드를 짜면 된다.
여기서 구현할 것은 ‘재귀 호출’, ‘균형 잡힌 문자열’ 판별, ‘올바른 문자열’ 판별이다.

균형 잡힌 문자열 판별은 맨 처음에 cnt를 0으로 초기화하고 문자열 가장 처음부터 순차적으로 읽어가면서 열기 괄호면 1을 더하고, 닫기 괄호면 1을 뺀다. 이후 cnt가 0인지 체크하여 0이면 종료한다.

올바른 문자열 판별은 균형 잡힌 문자열과 같은 방식으로 진행하되, cnt가 -1이 되는 순간이 존재한다면 올바르지 않는 것으로 판별하고, 그렇지 않으면 올바른 것으로 판별하면 된다.


정답 코드

def get_reverse(s):
ret = “”
for i in range(1, len(s) 1):
if s[i] == ‘(‘:
ret += ‘)’
else:
ret += ‘(‘
return ret
def is_correct(s):
cnt = 0
for c in s:
if c == ‘(‘:
cnt += 1
else:
cnt = 1
if cnt < 0:
return False
return True
def do(s):
if len(s) == 0:
return “”
i, cnt = 0, 0
while True:
if s[i] == ‘(‘:
cnt += 1
else:
cnt = 1
i += 1
if cnt == 0:
break
u, v = s[:i], s[i:]
if is_correct(u):
return u + do(v)
else:
return ‘(‘ + do(v) + ‘)’ + get_reverse(u)
def solution(p):
return do(p)
cs

Competition 카카오 블라인드 채용 문자열 압축

admin

Recent Posts

2024년 11월 17일 일요일 – 서울 생활 129주차

괌여행 아내와 함께 괌으로 여행을 갔다. 출산 이후로 둘만 가는 첫 여행이다. 하와이가 일본인들이 많이…

4일 ago

2024년 11월 3일 일요일 – 서울 생활 127주차

반복적인 일상 매일 아침 일어나 회사에 출근하고, 저녁을 먹고 돌아오는 일상의 반복이다. 주말은 가족을 보러…

3주 ago

2024년 10월 6일 일요일 – 서울 생활 123주차

Planning A well-structured plan has the following characteristics:   First, the ultimate vision you aim to…

2개월 ago

2024년 9월 29일 일요일 – 서울 생활 122주차

English The most common problem for English learners like myself is that we often use…

2개월 ago

2024년 9월 22일 일요일 – 서울 생활 121주차

추석 추석을 맞아 친가 외가 처가 어르신들을 모두 뵙고 돌아왔다. 아이가 태어난지는 좀 됐지만 한국에서…

2개월 ago

2024년 9월 8일 일요일 – 서울 생활 119주차

주말 이번주는 아내가 올라와서 주말을 함께 보냈다. 둘만 밥도 먹고 뮤지컬도 보고, 모임도 나가고 집에서…

2개월 ago

This website uses cookies.