[프로그래머스] 2020 KAKAO BLIND RECRUITMENT - "괄호 변환" (Java)

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

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

괄호변환

---

 

난이도 :  Level 2

 

 문제에서 구현 조건이 주어졌기에, 적절한 자료구조를 사용한 구현 능력을 요구하는 문제인 것 같습니다. 카카오는 주로 수학적인 알고리즘 능력을 요하는 것이 아닌, 자료구조를 활용한 구현 능력을 더 중요하게 보는 것 같습니다.   

 

 다음과 같은 로직으로 문제를 해결하였습니다. 

1. 올바른 괄호 문자열인지 판별하는 함수를 구현할 것.

2. 문제 조건에 따라 구현할 것.

 

 

- static int split;

 문자열 w를 문자열 u, v로 나누는 기준을 잡는 split 변수입니다. 올바른 괄호 문자열을 판별하는 isRight 함수에서 괄호 문자열이 되는 index + 1 한 값을 저장합니다. 

 

 

 

- String solution(String p)

 문자열 p를 입력으로 받습니다. 문제에 작성되어 있는 구현 조건인 2번에서 문자열 w를 u, v로 나눈다고 했는데, 설명되어 있는 w가 곧 p입니다. 카카오 문제는 설명이 굉장히 긴 경향이 있어서 입출력부터 읽게 되는데, 다시 자세히 읽지 않았으면 헷갈렸을겁니다. 

 

 문제에 주어진 문자열 w가 "균형잡힌 괄호 문자열"이라면 다음과 같은 과정을 통해 "올바른 괄호 문자열"로 변환할 수 있습니다. 아래에 작성된 구현 방법을 solution 함수에서 구현하였습니다. 

 

 

 

- boolean isRight(String p)

 "올바른 괄호 문자열"을 판별하는 함수입니다. 스택 자료구조를 사용하였습니다. "균형잡힌 괄호 문자열"이 되는 순간 return 하도록 하였으며, 스택에 저장되어 있는 괄호에 따라 "올바른 괄호 문자열"을 판별하도록 하였습니다. 

 

 

  코드

class Solution {
	static int split;
    public String solution(String p) {
        String answer = "";
        
        if (p.equals("")) return p;
        
        boolean right = isRight(p);
        
        // u,v로 분리.
        String u = p.substring(0, split);
        String v = p.substring(split, p.length());
        
        // 올바른 괄호 문자열이라면 3. 시행
        if(right) {
        	return u + solution(v);
        }
        
        // 올바른 괄호문자열이 아니라면 4. 시행
        answer= "(" + solution(v) + ")";
        	
        for(int i=1; i<u.length()-1; i++) {
        	if(u.charAt(i) == '(') {
        		answer += ")";
        	}
        	else answer += "(";
        }


        return answer;
    }
    
    // 올바른 괄호 문자열인지 판별.
    public boolean isRight(String p) {
    	Stack<Character> st = new Stack<>();
    	
    	boolean right = true;
    	int l = 0; 
    	int r = 0;
    	
    	for(int i=0; i<p.length(); i++) {
    		
    		if(p.charAt(i) == '(') {
    			l++;
    			st.push('(');
    		}
    		else {
    			r++;
    			if(!st.isEmpty()) {
    				st.pop();
    			}
    			else {
    				right = false; 
    			}
    		}
    		
    		if( l == r ) {
    			split = i + 1;
    			return right;
    		}
    	}
    	return right;
    }
}

 

 

 

 

피드백 환영합니다.