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

<문제>

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

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

<풀이>-재귀함수사용!!!

1.균형잡힌 괄호 문자열의 인덱스를 반환하는 함수 , 올바른 괄호 문자열인지 판단하는 함수를 만든다.

2.균형잡힌 괄호 문자열인지 판단하는 방법

-왼쪽괄호'(' 가 나올경우  count+1, 오른쪽 괄호')'가 나오는 경우 count-1을 해준다.

-만약 문자열에서 count=0이 되는 경우 그 인덱스까지의 문자열은 균형잡힌 괄호열이다.

#균형잡힌 괄호 문자열의 인덱스 반환
def balanced_index(p):
  count = 0 #왼쪽 괄호의 갯수
  for i in range(len(p)):
    if p[i] =='(':
      count+=1
    else : 
      count-=1
    if count == 0:
      return i

 

3.올바른 괄호 문자열인지 판단하는 방법

-왼쪽괄호'('가 나올경우 count+1을 해준다. 오른쪽괄호')'가 나올경우 count-1을 해준다.

-단, 반복문을통해 문자열을 돌면서 반복문이 끝나기전에 count가 0이 된다면 False를 반환한다.(올바른 괄호문자열이 아님)

#올바른 괄호 문자열인지 판단
def check_proper(p):
  count = 0 #왼쪽 괄호의 개수
  for i in p:
    if i=='(':
      count+=1
    else:
      if count == 0: #쌍이 맞지 않는 경우 False 반환
        return False
      count-=1
  return True

4.문제에 제시된 조건대로 올바른 괄호문자열로 만드는 과정을 수행한다.

->u와 v로 분리한 이후 u가 올바른 괄호 문자열인경우 v에 대해 처음부터 다시 수행한다는 조건이 있다. 이때 재귀함수를 사용한다.

 

<코드-파이썬>

#균형잡힌 괄호 문자열의 인덱스 반환
def balanced_index(p):
  count = 0 #왼쪽 괄호의 갯수
  for i in range(len(p)):
    if p[i] =='(':
      count+=1
    else : 
      count-=1
    if count == 0:
      return i

#올바른 괄호 문자열인지 판단
def check_proper(p):
  count = 0 #왼쪽 괄호의 개수
  for i in p:
    if i=='(':
      count+=1
    else:
      if count == 0: #쌍이 맞지 않는 경우 False 반환
        return False
      count-=1
  return True

def solution(p):
  answer=''
  if p == '':
    return answer
  index = balanced_index(p)
  u = p[:index+1]
  v = p[index+1:]
  #올바른 괄호 문자열 이면 v에 대해 함수를 수행한 결과를 붙여 반환
  if check_proper(u):
    answer = u + solution(v)
  #올바른 괄호 문자열이 아니라면 아래의 과정 수행
  else:
    answer = '('
    answer+=solution(v)
    answer+=')'
    u = list(u[1:-1])#첫번째와 마지막 문자 제거
    for i in range(len(u)):
      if u[i] == '(':
        u[i] = ')'
      else:
        u[i]='('
    answer+="".join(u)
  return answer

<코드-자바>

 

import java.util.*;
class Solution{
  public static void main(String[] args){
    System.out.println(solution("))((()"));
  }
  static String solution(String p){
    if(p.equals(""))
      return "";
    StringBuilder answer = new StringBuilder();
    StringBuilder sb = new StringBuilder(p);
    StringBuilder u = new StringBuilder();
    StringBuilder v = new StringBuilder();
    int open = 0;
    int close = 0;
    for(int i=0;i<sb.length();i++){
      if(sb.charAt(i)=='(')
        open++;
      if(sb.charAt(i)==')'){
        close++;
      }
      if(open == close){
        u.append(sb.substring(0,i+1));
        v.append(sb.substring(i+1));
        break;
      }
    }
    if(iscorrect(u.toString())){
      return u.append(solution(v.toString())).toString();
    }
    answer.append("(").append(solution(v.toString())).append(")");
    u.deleteCharAt(0);
    u.deleteCharAt(u.length()-1);
    answer.append(swap(u.toString()));
    return answer.toString();
  }
  static boolean iscorrect(String p){
    Stack<String> st = new Stack<>();
    for(String s:p.split("")){
      if(s.equals("(")) st.push(s);
      if(s.equals(")")&& !st.isEmpty())
        st.pop(); 
    }
    return st.size()<1;
  }
  static String swap(String a){
    StringBuilder swapString = new StringBuilder();
    for(char c:a.toCharArray()){
      if(c=='(')
        swapString.append(")");
      if(c==')')
        swapString.append("(");
    }
    return swapString.toString();
  }
}