[APS] 프로그래머스 60058. 괄호 변환 C++ 풀이 (substr)

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

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

 

 

 Problem 

1. '('와 ')'으로만 이루어진 길이 최대 1000의 문자열 p가 주어진다. 이 때, '('와 ')'의 개수는 동일하다.
2. 문자열 p에 대해 아래 과정을 반복한다.

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) 생성된 문자열을 반환합니다.

 

 

 Solution 

2020 KAKAO BLIND RECRUITMENT 문제 중 하나입니다. 카카오에서 문자열 다루는 문제는 필수적으로 나오는 것 같네요. 대개는 파이썬을 이용해서 풀면 편한 것들이 많지만, 해당 문제는 C++의 string의 substr 함수를 사용하면 C++로도 편하게 풀 수 있습니다. substr을 오랜만에 쓰다보니 기억이 안 나서 여기를 참고했습니다. 문제 자체가 길고 이해하기 쉬운 편은 아니지만, 시키는대로 구현하면 돼서 Level 2인 것 같습니다.

저는 함수가 총 세 가지 두었습니다. is_right와 make_str, 그리고 recur 입니다. 

• is_right 함수는 해당 문자열이 올바른 괄호 문자열인지 아닌지 판단하는 함수입니다. stack을 이용해서 구현했습니다. 올바른 괄호 문자열이면 true, 아니라면 false를 리턴합니다.
• make_str 함수는 위의 4단계에서 u를 가공하는 함수입니다. 앞뒤 괄호를 떼고 괄호의 방향을 바꾸어서 리턴합니다.
• recur 함수는 재귀적으로 수행해야하는 부분을 담당합니다. 입력으로 들어온 문자열을 u와 v로 나누고, u가 올바른 문자열인지 아닌지 여부에 따라 [3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다.]와 [4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다.] 두 가지 경우로 분기합니다.
  3으로 분기하는 경우 u는 그대로 둔 채 v에 대해서만 다시 recur 함수를 수행해주면 되므로 u + recur(v)가 되고, 4로 분기하는 경우 문제에서 시키는 대로 '(' + recur(v) + ')' + make_str(u)로 분기하면 됩니다.

자세한 구현은 아래 코드를 참고해주시면 되겠습니다 :)

 

 

 Code