[프로그래머스][Lv.2][JAVA][월간 코드 챌린지 시즌2]괄호 회전하기

 

문제

음 규칙을 지키는 문자열을 올바른 괄호 문자열이라고 정의합니다.

• (), [], {} 는 모두 올바른 괄호 문자열입니다.
• 만약 A가 올바른 괄호 문자열이라면, (A), [A], {A} 도 올바른 괄호 문자열입니다. 예를 들어, [] 가 올바른 괄호 문자열이므로, ([]) 도 올바른 괄호 문자열입니다.
• 만약 A, B가 올바른 괄호 문자열이라면, AB 도 올바른 괄호 문자열입니다. 예를 들어, {} 와 ([]) 가 올바른 괄호 문자열이므로, {}([]) 도 올바른 괄호 문자열입니다.

대괄호, 중괄호, 그리고 소괄호로 이루어진 문자열 s가 매개변수로 주어집니다. 이 s를 왼쪽으로 x (0 ≤ x < (s의 길이)) 칸만큼 회전시켰을 때 s가 올바른 괄호 문자열이 되게 하는 x의 개수를 return 하도록 solution 함수를 완성해주세요.

---

제한사항

• s의 길이는 1 이상 1,000 이하입니다.

---

입출력 예

 

---

 

분석

1. 괄호의 짝이 알맞게 이어진 경우는 올바른 괄호 문자열이다.
2. 이 때, "짝이 알맞게"의 개념은 여는 괄호와 닫는 괄호의 종류가 대칭이 되는 것이다.
3. "x만큼 회전"이라 함은 문자열 s에서 앞의 x개의 문자열을 뒤로 옮기는 것을 의미한다.
4. (1) 문자열을 가지고 0부터 (s의 길이 - 1)만큼 반복하는 for문으로 문자열을 회전시키면서,
   (2) 각 반복마다 만들어진 문자열이 올바른 괄호 문자열인지를 판단하여
   (3) answer에 더한다. 
5. 올바른 괄호인지를 판단하기 위한 알고리즘은 stack을 사용하면 되지 않을까.
   (1) 일단은 여는 괄호가 오면 stack에 쌓고,
   (2) 닫는 괄호가 오면 stack에 가장 마지막으로 쌓인 요소를 꺼내어 짝이 맞는지 비교하여
   (3) 짝이 맞으면 꺼낸 stack을 없애고 다음 문자를 검증,
   (4) 짝이 안 맞으면 바로 false
   (5) 이것을 반복하여 남은 문자가 없으면 true

 

 

 

 

---

 

피드백

1. 다른 사람의 풀이를 보니 대략적인 구조(stack을 쓴다던지)는 다들 비슷한데, 세밀한 부분에서 가지각색으로 푸는 것 같다. 여닫는 괄호를 어떻게 구분할 것인지와 그 짝을 어떻게 검증하는지가 보통 다르다. 
2. 다른 사람의 코드와 비교해보니 내 부족한 점이 아직도 많다. 비교한 내용은 [다른 사람의 코드] 부분 접은 글 참고.

 

 

 

---

 

답안

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

class Solution {
    public int solution(String s) {
        int answer = chkBrakeRight(s)? 1 : 0;
        
        // 0부터 (s의 길이 - 1)만큼 반복
        for(int i = 0; i < s.length()-1; i++) {
        	// 문자열 왼쪽으로 회전시키기
        	if(i >= 0) {
        		s = s.substring(1, s.length()) + s.charAt(0);
        	}
        	
        	// 문자 검증 
        	boolean rightChk = chkBrakeRight(s);
            
            // 검증값이 true 라면 증가
            if(rightChk)    answer++;
        }
        return answer;
    }
    
    // 변수로 들어온 문자열이 올바른 괄호 문자인지 검증하는 메서드
    public static boolean chkBrakeRight(String s) {
    	boolean chkRight = true;

        // 여는 괄호는 양수, 닫는 괄호는 음수이며
        // 짝에 맞게 숫자를 지정함(여는 괄호 + 닫는 괄호 = 0이 되도록)
        Map<String, Integer> braketMap = new HashMap();
        braketMap.put("(", 1);
        braketMap.put("[", 2);
        braketMap.put("{", 3);
        braketMap.put(")", -1);
        braketMap.put("]", -2);
        braketMap.put("}", -3);

    	// 올바른 괄호 문자열인지 판별하는 데 사용될 변수
    	Stack<String> st = new Stack();
    	
        for(int j = 0; j < s.length(); j++) {
    		String chk = s.charAt(j) + "";
    		// 1-1. 여는 괄호일 경우 stack에 쌓는다.
    		if(braketMap.get(chk) > 0) {
    			st.push(chk);
    			
    		// 1-2. 닫는 괄호일 경우 stack에 쌓인 요소로 검증한다.
    		}else {
    			// 2-1. stack이 비어있는 경우 올바르지 않음.
    			if(st.isEmpty()) {
    				chkRight = false;
    				break;
    				
    			// 2-2. stack에 값이 있는 경우 검증 진행
    			}else {
    				// 마지막 값의 value와 검증값의 value를 더해 0이 되지 않으면 올바르지 않음.
    				String lastEle = st.pop();
    				if(braketMap.get(lastEle) + braketMap.get(chk) != 0) {
    					chkRight = false;
    					break;
    				}
    			}
    		}
    	}
        // 모든 문자를 순회한 뒤 stack에 요소가 남아있다면 올바르지 않음.
        if(!st.isEmpty()) {
        	chkRight = false;
        }
        
    	return chkRight;
    }
}

 

 

 

---

 

다른 사람의 답안

import java.util.Stack;

class Solution {
    private final Stack<Character> stack = new Stack<>();

        public int solution(String s) {
            int answer = 0;
            StringBuilder stringBuilder = new StringBuilder(s);

            for (int i = 0; i < s.length(); i++) {
                stringBuilder.append(stringBuilder.charAt(0));
                stringBuilder.deleteCharAt(0);
                if (correctParenthesis(stringBuilder.toString().toCharArray()))
                    answer++;
            }
            return answer;
        }

        private boolean correctParenthesis(char[] s) {
            for (char c : s) {
                if (!(check(c, '(', ')') && check(c, '[', ']') && check(c, '{', '}')))
                    return false;
            }
            return stack.isEmpty();
        }

        private boolean check(char c, char a, char b) {
            if (c == a)
                stack.push(a);
            else if (c == b)
                if (!stack.isEmpty() && stack.peek() == a) stack.pop(); else return false;
            return true;
        }
}

 

 

위의 코드(코드B)와 내가 통과한 코드(코드A)를 챗지에게 비교해달라고 했는데, 모든 부분에서 위의 코드가 압승이었다. 나쁘지 않다고 생각했는데 좋지도 않은 코드였던 거군. 더 정진하자...

 

 

가독성

• 코드 A:
  • 괄호 매핑을 HashMap을 사용하여 명시적으로 처리합니다.
  • chkBrakeRight 메서드에서 괄호의 올바름을 검증하는 로직이 명확하게 분리되어 있어 이해하기 쉬움.
  • 문자열 회전과 검증 로직이 분리되어 있지만, 문자열 회전 및 substring 사용이 비효율적일 수 있음.
• 코드 B:
  • StringBuilder를 사용하여 문자열을 효율적으로 회전시키는 접근법을 사용함.
  • 괄호 검증 로직이 check 메서드로 간단하게 처리되어 있어 가독성이 좋음.
  • Stack을 전역으로 사용하여 중복 검사 로직을 간단히 함.

시간적 효율성

• 코드 A:
  • substring과 문자열 연결을 사용하여 문자열 회전. 이 작업은 O(n^2) 시간이 소요됨 (문자열 길이가 n일 때 substring의 사용이 매 회전마다 O(n) 시간 복잡도를 가짐).
  • 각 회전마다 chkBrakeRight를 호출하여 O(n)의 시간 복잡도를 가지므로, 전체적으로 O(n^2).
• 코드 B:
  • StringBuilder를 사용하여 문자열 회전을 O(n)으로 수행함. append와 deleteCharAt이 효율적임.
  • correctParenthesis 검증 메서드는 O(n)의 시간 복잡도를 가짐.
  • 전체적으로 O(n^2) 시간 복잡도지만, 문자열 회전이 더 효율적임.

메모리적 효율성

• 코드 A:
  • HashMap과 Stack을 사용하여 메모리를 사용함.
  • 문자열 회전과 검증 로직에서 문자열 복사가 발생하여 메모리 사용량이 증가할 수 있음.
• 코드 B:
  • Stack을 전역으로 사용하여 메모리를 절약함.
  • StringBuilder를 사용하여 문자열 회전 시 메모리 효율적임.
  • 전역 Stack을 사용하여 반복문 내에서 메모리 재사용이 가능함.

결론

• 가독성: 코드 B는 전반적으로 더 간결하고 이해하기 쉬운 구조를 가지고 있습니다.
• 시간적 효율성: 코드 B가 문자열 회전과 검증을 더 효율적으로 수행합니다.
• 메모리적 효율성: 코드 B는 StringBuilder를 사용하여 메모리 사용을 최적화하며, 전역 Stack을 재사용하여 메모리 사용을 줄입니다.

결론적으로, 코드 B는 가독성, 시간적 효율성, 메모리적 효율성 측면에서 더 우수한 접근법을 제공한다고 할 수 있습니다.

 

 

 

/*
	난 if문을 여러 개를 쓰고 그 안에서 또 &&로 조건을 줘서 괄호의 짝을 맞추는게
    가독성이나 여러가지 부분에서 효율적인가 의심이 들어서
    별도 Map을 만들고 그 value로 더한 값을 검증하는 방식을 썼는데,
    막상 보니까 이런 방법도 나쁘지 않은 것 같다. 
    
    회전이 0인 경우를 위해 나는 아예 검증 메서드를 따로 분리하고
    answer 의 초기값 할당에서부터 그 메서드를 호출하는 식으로 했는데,
    이렇게 맨 뒤로 빼고 대신 for문을 length-1이 아니라 length까지로 하면 되는구나.
    또 생각이 짧았던 부분이 이렇게 발견되는군.
*/

import java.util.Stack;

class Solution {
    public int solution(String s) {
        Stack<Character> stack = new Stack<>();
        int answer = 0;
        int N = s.length();
        for(int x = 0 ; x < N ; x++){
            stack.clear();
            for(int y = 0 ; y < N ; y++){
                if(!stack.isEmpty()){
                    if(stack.peek() == '(' && s.charAt(y) == ')'){
                        stack.pop();
                    }
                    else if(stack.peek() == '[' && s.charAt(y) == ']'){
                        stack.pop();
                    }
                    else if(stack.peek() == '{' && s.charAt(y) == '}'){
                        stack.pop();
                    }
                    else
                        stack.push(s.charAt(y));
                }
                else
                    stack.push(s.charAt(y));
            }
            if(stack.isEmpty()){
                answer++;
            }
            char data = s.charAt(0);
            s = s.substring(1, N);
            s += data;
        }
        return answer;
    }
}

 

 

 

---

 

🔗링크

프로그래머스