[JAVA] 프로그래머스 2020 KAKAO BLIND RECRUITMENT - 괄호 변환

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

문제 이해

문자열은 ( 와 ) 로만 이루어져 있다.

문자열은 대부분 괄호의 개수는 맞다.( ‘(’의 개수 = ‘)’의 개수) 하지만 괄호 짝 위치가 틀린게 많다.

• 균형잡힌 괄호 문자열 : 괄호 개수가 같고, 짝은 다른 경우
• 올바른 괄호 문자열 : 괄호 개수도 같고, 짝도 맞는 경우

우리는 올바른 괄호 문자열로 만들려고 한다.

입력문자로 p가 들어온다.

1. p 문자가 올바른 괄호 문자열 → 정답이므로 바로 반환
2. p 문자가 균형잡힌 괄호 문자열
   1. p문자를 u와 v로 나눔 (u는 균형잡힌 괄호 문자열이어야 함)
   2. u가 올바른 괄호 문자열 → v를 p로 두고 다시 1번부터 확인함
   3. u가 균형잡힌 괄호 문자열 → “(” + v를 p로 두고 다시 1번부터 확인한 문자열 + “)” + u의 첫문자와 마지막 문자 제거하고 나머지 문자열을 다 뒤집은거
   
   

문제 이해하는데에만 20분정도 걸렸다 .....

문제 풀이

문제를 보고 재귀가 필요하다고 느꼈다. 그래서 기능별로 메소드를 만들었다.

• public String solution(String p) 입력값 받고 정답 리턴하는 메소드

• String remakeU(String u) u가 올바른 괄호 문자열이 아닐 때 만드는 새로운 문자열

  • u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙임

• int divide(String p) p 문자열을 u, v로 나눠줌

  • (개수와 )개수가 처음 같을 때 그 때의 index를 리턴해줌

• boolean correct(String s) 올바른 괄호 문자열인지 확인

  • s가 빈 문자열이면 true 리턴
  • 스택을 사용하여 올바른지 확인함

코드

//프로그래머스 통과 코드
import java.util.Stack;
class Solution {
    public String solution(String p) { //입력값 받고 정답 리턴하는 메소드
        String answer = "";
		if(correct(p)) return p; //올바른 괄호 문자열이면 바로 답으로 리턴
		
		//올바른 괄호 문자열 아닐때
		
		//문자열 분리
		int divideNum = divide(p); //분리할 index 받아옴
		String u = p.substring(0, divideNum);
		String v = p.substring(divideNum, p.length());
		
		if(correct(u)) { //u가 올바른 괄호 문자열이면
			answer = answer + u;
			if(!correct(v)) {
				answer += solution(v); //v의 올바른 괄호 문자열을 찾기 위해 solution 재귀 돌려줌
			}
		}
		else { //u가 균형잡힌 괄호 문자열이면
			answer += "(";
			answer += solution(v); 
			answer += ")";
			answer += remakeU(u); //u 문자열을 변형해줌
		}
		return answer;
    }
    
    static String remakeU(String u) { //u가 올바른 괄호 문자열이 아닐 때 만드는 새로운 문자열
		String reU = "";
		for(int i=1; i<u.length()-1; i++) { //앞뒤 글자 하나씩은 순회하지 않고 뒤집어줌
			if(u.charAt(i) == '(') reU += ")";
			else if(u.charAt(i) == ')') reU += "(";
		}
		return reU;
	}
    
	static int divide(String p) { //p 문자열을 u, v로 나눠줌
		int left=0, right=0; //(개수와 )개수 확인하기 위함
        
		for(int i=0; i<p.length(); i++) {
			if(p.charAt(i)=='(') left++;
			else if(p.charAt(i)==')') right++;
			
			if(left == right) { //(개수와 )개수가 같으면 균형잡힌 문자열이므로 리턴
				return i+1;
			}
		}
		return p.length();
	}
    
	static boolean correct(String s) { //올바른 괄호 문자열인지 확인
		if(s.equals("")) return true; //빈 문자열이면 올바름
		
		boolean ans = true;
		Stack<Character> stack = new Stack<>();
		for(int i=0; i<s.length(); i++) {
			if(s.charAt(i)=='(') {
				stack.add('(');
			}else {
				if(stack.isEmpty() || stack.peek() != '(') {
					ans = false; break;
				}else {
					stack.pop();
				}
			}
		}
		
		return ans;
	}
    
}

//이클립스로 돌린 코드
package pr;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;

public class pr_괄호변환 {
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String p = br.readLine();
		
		System.out.println(solution(p));
		
	}
	static String solution(String p) { //입력값 받고 정답 리턴하는 메소드
		String answer = "";
		if(correct(p)) return p; //올바른 괄호 문자열이면 바로 답으로 리턴
		
		//올바른 괄호 문자열 아닐때
		
		//문자열 분리
		int divideNum = divide(p); //분리할 index 받아옴
		String u = p.substring(0, divideNum);
		String v = p.substring(divideNum, p.length());
		
		if(correct(u)) { //u가 올바른 괄호 문자열이면
			answer = answer + u;
			if(!correct(v)) {
				answer += solution(v); //v의 올바른 괄호 문자열을 찾기 위해 solution 재귀 돌려줌
			}
		}
		else { //u가 균형잡힌 괄호 문자열이면
			answer += "(";
			answer += solution(v); 
			answer += ")";
			answer += remakeU(u); //u 문자열을 변형해줌
		}
		return answer;
	}
	
	static String remakeU(String u) { //u가 올바른 괄호 문자열이 아닐 때 만드는 새로운 문자열
		String reU = "";
		for(int i=1; i<u.length()-1; i++) {  //앞뒤 글자 하나씩은 순회하지 않고 뒤집어줌
			if(u.charAt(i) == '(') reU += ")";
			else if(u.charAt(i) == ')') reU += "(";
		}
		return reU;
	}
	
	static int divide(String p) { //p 문자열을 u, v로 나눠줌
		int left=0, right=0; //(개수와 )개수 확인하기 위함
		for(int i=0; i<p.length(); i++) {
			if(p.charAt(i)=='(') left++;
			else if(p.charAt(i)==')') right++;
			
			if(left == right) { //(개수와 )개수가 같으면 균형잡힌 문자열이므로 리턴
				return i+1;
			}
		}
		return p.length();
	}
	
	static boolean correct(String s) { //올바른 괄호 문자열인지 확인
		if(s.equals("")) return true; //빈 문자열이면 올바름
		
		boolean ans = true;
		Stack<Character> stack = new Stack<>();
		for(int i=0; i<s.length(); i++) {
			if(s.charAt(i)=='(') {
				stack.add('(');
			}else {
				if(stack.isEmpty() || stack.peek() != '(') {
					ans = false; break;
				}else {
					stack.pop();
				}
			}
		}
		
		return ans;
	}
}