[프로그래머스] 괄호 회전하기 76502 (Level 2) - C++

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

프로그래머스

 

📌 문제 핵심 요약

• 문자열 s가 주어질 때
• 문자열을 왼쪽으로 0칸 ~ length-1칸 회전
• 각 회전 결과가 올바른 괄호 문자열이면 카운트

괄호 종류: (), {}, []

입출력 예 #1

입력 : "[](){}" 

x	s를 왼쪽으로 x칸만큼 회전	올바른 괄호 문자열?
0	"[](){}"	O
1	"](){}["	X
2	"(){}[]"	O
3	"){}[]("	X
4	"{}[]()"	O
5	"}[](){"	X

올바른 괄호 문자열이 되는 x가 3개이므로, 3을 return 해야 한다.

---

💭 처음 문제 접근

문제를 보자마자 떠오른 생각은 단순했다.

괄호 짝 맞추기네 → 스택 쓰면 되겠다

• 여는 괄호 → 스택에 push
• 닫는 괄호 → 스택 top과 짝이 맞는지 확인
• 끝까지 검사 후 스택이 비어 있으면 성공

괄호 종류가 여러 개여도
닫는 괄호는 항상 바로 이전의 열린 괄호와 짝이 맞아야 한다는 점은 동일하다.

👉 기존 괄호 문제 로직에
👉 “문자열을 회전하면서 반복”만 추가하면 된다고 생각했다.

---

❌ 처음에 작성했던 코드 (틀린 코드)

 

#include <string>
#include <vector>
#include <stack>

using namespace std;

bool check_opening(char c){
    if(c=='(' || c=='[' || c== '{') return true;
    else return false;
}

bool check_false(char a, char b){
    if(a=='(' && b ==')') return false;
    else if(a=='{' && b =='}') return false;
    else if(a=='[' && b ==']') return false;
    return true;
}

int solution(string s) {
    int answer = 0;

    int l= s.length();
    for(int i=0;i<l;i++){
        stack<char> st;
        int idx=i;
        int j=0;
        bool success=true;
        while(j<l){
            if(check_opening(s[idx])) st.push(s[idx]);
            else{
            if(st.empty()){
                success=false;
                break;
            }
            char tmp= st.top();
            st.pop();
            if(success=check_false(tmp, s[idx])) break;    
            j++;
            }
        }
        if(st.empty() && success) answer++;
    }
    return answer;
}

문제는 로직 자체보다 루프 제어였다.

• 인덱스 증가 조건이 꼬임
• continue, break 때문에
  인덱스 업데이트가 건너뛰어지는 경우 발생
• 일부 케이스만 검사하고 루프가 끝나버림

👉 이 상태로는 끝까지 검증이 안 되는 회전 케이스가 생김

---

 계속 틀렸던 이유

핵심 원인은 이것이었다.

루프 안에서 제어권을 이동시키면서,
인덱스 증가 로직이 항상 실행된다고 착각함

특히 이런 구조가 문제였다.

• 조건 만족 → continue
• 하지만 그 아래에 있던 idx++, j++이 실행되지 않음
• 결과적으로 같은 문자를 계속 보거나
• 아예 검사해야 할 문자를 건너뜀

👉 초반 몇 개 케이스만 맞고, 나머지는 계속 실패
👉 그래서 반례를 찾기도 더 어려웠음

---

✅ 수정 후 정답 코드

핵심 수정 포인트는 다음과 같다.

• 인덱스 증가를 한 곳에서만 관리
• 회전 처리는 idx % length
• 성공/실패 플래그를 명확하게 유지

 

#include <string>
#include <vector>
#include <stack>

using namespace std;

bool check_opening(char c){
    if(c=='(' || c=='[' || c== '{') return true;
    else return false;
}

bool check(char a, char b){
    if(a=='(' && b ==')') return true;
    else if(a=='{' && b =='}') return true;
    else if(a=='[' && b ==']') return true;
    return false; 
}

int solution(string s) {
    int answer = 0;

    int l= s.length();
    
    for(int i=0;i<l;i++){
        stack<char> st;
        int idx=i;
        int j=0;
        bool success=true;
        while(j<l){
            if(check_opening(s[idx%l])) st.push(s[idx%l]);
            else{
                if(st.empty()){
                success=false;
                break;
                }
                char tmp= st.top();
                if(check(tmp, s[idx%l])) {
                    st.pop();
                }
                else {
                    success= false; 
                    break;
                }
                }
            j++;
            idx++;
        }
        if(st.empty() && success) answer++;
    }
    return answer;
}

---

이번 문제에서 배운 점 

루프 안에서 제어권을 사용할 때 반드시 확인할 것

continue / break가
업데이트 로직을 건너뛰지는 않는가?

특히 while문에서는 더 위험하다.

✔ 해결 방법

• 인덱스 증가를 루프 조건에 포함
• 또는 for문으로 구조를 단순화
• 업데이트 로직을 분기문 밖으로 이동

---

코드 개선 아이디어 (STL 활용)

내 구현은 함수로 괄호 짝을 직접 비교했지만,
STL을 쓰면 더 간결하게 쓸 수도 있다.

 

unordered_map<char, char> bracketPair = {{')','('}, {']','['},{'}','{'}}
bracketPair.count(ch) //ch가 닫힌 괄호인 경우 간단하게
st.top()!=bracketPair[ch] //top의 원소가 짝이 맞는 열린 괄호인

• map은 정렬 필요 없음 → unordered_map 적합
• 시간 복잡도는 동일
• 가독성은 더 좋아질 수 있음

👉 코테에서는 반드시 STL을 써야 하는 건 아니지만
👉 이런 패턴을 알고 있으면 코드가 훨씬 깔끔해진다.

---

개인 문제풀이 레포

https://github.com/zzmnxn/algorithm-study