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

3 분 소요

업데이트:

문제

프로그래머스-괄호변환
괄호 문자열을 입력받아서 올바른 순서대로 배치된 괄호 문자열을 알려주는 코드를 작성하는 문제.

균형잡힌 괄호 문자열을 입력받아 올바른 괄호 문자열로 변환하기

  • 설명
    • 균형잡힌 괄호 문자열
      ‘(‘와 ‘)’의 갯수가 같은 경우
    • 올바른 괄호 문자열
      ‘(‘과) ‘)’의 갯수가 같고, 짝도 모두 맞는 경우

    균형잡힌 괄호 문자열 의 경우 다음과 같은 작성을 통해 올바른 괄호 문자열로 변환할 수 있다.

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

풀이

생성 함수 목록 및 설명

  • private boolean isCorrect(String p);
    설명 : 올바른 괄호 문자열인지 판단하는 함수
    매개변수 : 판단할 문자열
    동작 내용 : p의 한 글자씩 반복하면서 ‘(‘는 1 증가, ‘)’는 1 감소
    0보다 작아지거나, 반복 종료 후 0이 아닌경우 올바른 괄호 문자열이 아니다.
    리턴 값 : 올바른 괄호 문자열인지 판단 결과

  • private String creation(String w);
    설명 : 균형잡힌 괄호 문자열올바른 괄호 문자열로 변환하는 함수
    매개변수 : 균형잡힌 괄호 문자열
    동작 내용 : 문제에서 주어진 균형잡힌 괄호문자열올바른 괄호 문자열로 변환하는 내용을 수행한다.
    리턴 값 : 생성된 올바른 괄호 문자열

  • private String[] seperate(String w);
    설명 : 균형잡힌 괄호 문자열을 u,v로 분리하는 함수
    매개변수 : 균형잡힌 괄호 문자열 혹은 문자열
    동작 내용 : 입력받은 문자열 w에서 균형잡힌 문자열까지의 idx를 찾는다.
    idx를 기준으로 u, v로 분리해서 배열에 담는다.
    리턴 값 : u, v가 담긴 string 배열
    ( u: 균형잡힌 괄호문자열로 더이상 분리할 수 없음, w에서 u를 제외한 문자열)

소스코드

class Solution {
	public String solution(String p) {
		return creation(p);
	}

	private boolean isCorrect(String p) {
		// TODO Auto-generated method stub
		int chk = 0;
		for (int i = 0; i < p.length(); i++) {
			if (p.charAt(i) == '(') {
				chk++;
			} else {
				chk--;
				if (chk < 0) {
					return false;
				}
			}
		}
		return chk == 0 ? true : false;
	}

	private String creation(String w) {
//	1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다. 
		if (w.trim().equals("")) {
			return "";
		}
		if (isCorrect(w)) {
			return w;
		}
//	2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다. 
		String[] sep = seperate(w);

//	3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다. 
		if (isCorrect(sep[0])) {
			String result_v = creation(sep[1]);
//	  3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다. 
			return sep[0] + result_v;
		}

//	4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다. 
		else {
//	  4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다. 
			StringBuilder sb = new StringBuilder();
			sb.append("(");
//	  4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다. 
			sb.append(creation(sep[1]));
//	  4-3. ')'를 다시 붙입니다. 
			sb.append(")");
//	  4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다. 
			for (int i = 1; i < sep[0].length() - 1; i++) {
				if (sep[0].charAt(i) == '(') {
					sb.append(")");
				} else {
					sb.append("(");
				}
			}
//	  4-5. 생성된 문자열을 반환합니다.
			return sb.toString();
		}
	}

	private String[] seperate(String w) {
		// TODO 균형잡힌 문자열로, 더이상 분리가 불가능함
		String[] ans = new String[2];
	// 1. 괄호의 갯수가 일치해야함
		int left = -1;
		int right = 0;
		int idx = 0;
		while (idx<w.length() && left != right) {
			if (w.charAt(idx++) == '(') {
				if(left==-1) {
					left=0;
				}
				left++;
			} else {
				right++;
			}

		}
		if(left==right) {
			ans[0]=w.substring(0,idx);
			ans[1]=w.substring(idx,w.length());
		}else {
			ans[1]=w;
		}
		return ans;
	}
}

댓글남기기