[프로그래머스/JAVA] 괄호 회전하기

https://school.programmers.co.kr/learn/courses/30/lessons/76502

프로그래머스

📌 문제 요약 

 

주어진 문자열을 왼쪽으로 x칸씩 회전하며 올바른 괄호 문자열이 되는 경우를 찾아야 하는 문제입니다. 올바른 괄호 문자열의 정의는 다음과 같습니다:

1. (), [], {}는 올바른 괄호 문자열입니다.
2. A가 올바른 괄호 문자열이라면, (A), [A], {A}도 올바른 괄호 문자열입니다.
3. A, B가 올바른 괄호 문자열이라면, AB도 올바른 괄호 문자열입니다.

---

[ 오답 노트 ]

❌ 기존 오답 코드

import java.util.*;

class Solution {
    public int solution(String s) {
        int answer = 0;
        
        for(int i = 0; i < s.length(); i++) {
            StringBuilder sb = new StringBuilder();
            sb.append(s); // sb = "[](){}"
            // [](){}      ->   ](){}[   
            // 인덱스 0의 값 -> 인덱스 5의 값
            // 인덱스 1의 값 -> 인덱스 0의 값
            // 인덱스 2의 값 -> 인덱스 1의 값
            // ...
            // 인덱스 5의 값 -> 인덱스 4의 값
            for(int j = 0; j < sb.length(); j++) {
                sb.setCharAt(j, sb.charAt(sb.length()-1-j));
            } // sb = "](){}["
            
            // 올바른 괄호 문자열인지 판별
            Stack<Character> st = new Stack<>();
            for(int z = 0; z < sb.length(); z++) {
                if(sb.charAt(z) == '{' || sb.charAt(z) == '(' || sb.charAt(z) == '[') {
                    st.push(sb.charAt(z));
                }else{ // sb.charAt(i) == '}' || sb.charAt(i) == ')' || sb.charAt(i) == ']'
                    if(st.isEmpty()) {
                        continue;
                    }
                    st.pop();
                }
            }
            
            if(st.isEmpty()) {
                answer += 1;
            }
            
        }
        
        return answer;
    }
}

📌 기존 코드의 문제점

 

1. 문자열 회전 방식 오류

 

문제에서는 "문자열을 왼쪽으로 x칸 회전"해야 하지만, 기존 코드인  sb.setCharAt(j, sb.charAt(sb.length()-1-j));은 문자열을 반대로 뒤집는 방식(역순 문자열 생성)으로 처리하고 있다. 

아래와 같은 방식으로 s.substring(i)로 인덱스 i부터 끝까지의 문자열과 s.substring(0,i)를 사용해 맨 처음 인덱스부터 i-1까지의 문자열을 합치면 왼쪽으로 i칸 회전한 결과가 된다.

// 문자열 회전
String rotated = s.substring(i) + s.substring(0, i);

 

 

2. 올바른 괄호 판별 로직 오류

 

stack을 사용하는 방식은 맞지만 닫는 괄호(],),}) 가 올바른 짝인지 확인하지 않았다. 기존 코드는 스택이 비어있지만 않으면 올바른 짝이라고 생각하고 pop해서 없애게 되어있어 올바른 로직이 아니다. 

 

아래와 같이 st.peek()의 값이 여는 괄호([,(,{) 가 되면 pop하도록 하는 조건을 추가해야 한다. 

각 괄호마다 짝이 맞아야 되므로 (c == '}' && 조건도 각각 추가해야 된다. 

 

또한 flag 변수를 추가해서 괄호 문자열 검증 과정에서 올바르지 않은 상태를 발견하면 추가 검사를 하지 않도록 한다. 

 boolean flag = true; // 처음에는 유효하다고 가정
 ...
 } else {
                    if (st.isEmpty() || 
                        (c == '}' && st.peek() != '{') || 
                        (c == ')' && st.peek() != '(') || 
                        (c == ']' && st.peek() != '[')) {
                        flag = false; // 유효하지 않음으로 상태 변경
                        break;
                    }
                    st.pop();
        }
        // 유효한 경우에만 처리
             if(flag && st.isEmpty()) {
                answer++;
            }
        }

 

 

3. 효율성 문제

 

StringBuilder를 매번 생성하고 회전처리를 수행하기 때문에 문자열 길이가 길이가 길어질수록 성능이 저하된다. 

 

---

[ 정답 코드 & 올바른 풀이 ]

📌 정답 코드

import java.util.*;

class Solution {
    public int solution(String s) {
        int answer = 0;
        // 1. 문자열 회전
        for(int i = 0; i < s.length(); i++) {
            String rotated = s.substring(i) + s.substring(0,i);
            // 2. 올바른 괄호 판별
            Stack<Character> st = new Stack<>();
            boolean flag = true;

            for(int j = 0; j < rotated.length(); j++) {
                char c = rotated.charAt(j);
                if(c == '[' || c == '{' || c == '(') {
                    st.add(c);
                }else { // 다 닫는 괄호
                    if(st.isEmpty() ||
                        (c == '}' && st.peek() != '{') || 
                        (c == ')' && st.peek() != '(') || 
                        (c == ']' && st.peek() != '[')) {
                        flag = false;
                        break;
                    }
                    st.pop();
                }
            }

            if(flag && st.isEmpty()) {
                answer++;
            }
        }

        return answer;
    }
}