[KAKAO_BLIND_RECRUITMENT_2020] 괄호 변환

문제

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

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

 

 

출제 의도

tech.kakao.com/2019/10/02/kakao-blind-recruitment-2020-round1/

• 주어진 로직을 그대로 구현할 수 있는지 파악
• 재귀함수를 이해하고 작성할 수 있는지 파악

 

 

풀이

• 문제에서 제시하는 조건의 길이가 길고 세세하다.
  이러한 문제는 경험상 대부분 문제의 조건을 구대로 구현하는 것을 요구한다. 
• 문자열의 경우 index의 범위를 항상 조심.
• 올바른 괄호 문자열 판단은 별도의 메소드로 설계.
• 요구 사항에 재귀 호출이 있으므로, dfs로 설계.
• 리버스와 삭제등이 빈번하므로 String보다는 StringBuilder를 사용.

 

 

과정

문제의 과정은 문제에 있는 것과 동일,  이해가 되지않는다면,
이 글 상단에 있는 문제 링크를 통해 해당 페이지의 하단에 있는 과정을 하나하나 따지면서 보길 권장.
→ 밑의 코드에 과정에 해당하는 곳을 주석처리하여 삽입했습니다.

1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다.
2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다.
   단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다.
3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다.
   1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다.
4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다.
   1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다.
   2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다.
   3. ')'를 다시 붙입니다.
   4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다.
   5. 생성된 문자열을 반환합니다.

 

 

 

알고리즘 지식

• String
• Stack

 

 

JAVA코드

 package KAKAO_BLIND_RECRUITMENT_2020;

import java.util.Stack;

public class KAKAO_괄호변환 {

	public static void main(String[] args) {
		// String p = "(()())()";
		// String p = ")(";
		String p = "()))((()";
		String answer = "";
		answer = dfs(p);

		System.out.println(answer.length() == 0 ? "" : answer);
	}

	private static String dfs(String p) {
//		2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다. 
		StringBuilder u = new StringBuilder();
		StringBuilder v = new StringBuilder(p);
		int start = 0;
		int end = 0;

		for (int i = 0; i < p.length(); i++) {

			char c = p.charAt(i);

			// u,v 갱신
			u.append(c);
			v.deleteCharAt(0);

			// 괄호의 갯수 체크
			if (c == '(') {
				start++;
			} else {
				end++;
			}

			// 괄호의 갯수가 같다 = 균형잡힌 괄호 문자열
			if (start == end) {

//				3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다. 
				if (isValid(u.toString())) {
					// v에 대해 dfs
					String temp = dfs(v.toString());
					u.append(temp);

//				 	 3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다. 
					return u.toString();
				}
//				4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다. 
				else {
					StringBuilder temp = new StringBuilder();

//				 	 4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다. 
					temp.append("(");
//				 	 4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다. 
					temp.append(dfs(v.toString()));
//				 	 4-3. ')'를 다시 붙입니다. 
					temp.append(")");
//				 	 4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다. 
					u.deleteCharAt(0);
					u.deleteCharAt(u.length() - 1);

					// 괄호 방향 뒤집기
					for (int idx = 0; idx < u.length(); idx++) {
						if (u.charAt(idx) == '(') {
							u.replace(idx, idx + 1, ")");
						} else {
							u.replace(idx, idx + 1, "(");
						}
					}

					temp.append(u);
					u = temp;
//				 	 4-5. 생성된 문자열을 반환합니다.
					return u.toString();
				}
			}
		}

//		1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다. 
		return u.toString();
	}

	// '올바른 괄호 문자열' 판단
	private static boolean isValid(String p) {
		Stack<Character> s = new Stack<Character>();
		s.push(p.charAt(0));

		for (int i = 1; i < p.length(); i++) {
			char c = p.charAt(i);
			if ((c == ')') && (s.peek() == '(')) {
				s.pop();
			} else {
				s.push(c);
			}
		}

		// stack이 비었다면 '올바른 괄호 문자열'
		if (s.isEmpty()) {
			return true;
		} else {
			return false;
		}
	}
}