프로그래머스 76502 - 괄호 회전하기

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

using namespace std;

unordered_map<char, char> bracketPair = { {')', '('}, {']', '['}, {'}', '{'} };

bool isValid(string &s, int start) {
    stack<char> stk;
    unsigned int sz = s.size();
    
    for (int i = 0; i < sz; i++) {
        char ch = s[(start + i) % sz];
        
        if (bracketPair.count(ch)) {
            if (stk.empty() || stk.top() != bracketPair[ch])
                return false;
            
            stk.pop();
        } else {
            stk.push(ch);
        }
    }
    
    return stk.empty();
}

int solution(string s) {
    int answer = 0;
    int n = s.size();
    
    for (int i = 0; i < n; i++) {
        answer += isValid(s, i);
    }
    
    return answer;
}

💡

• map과 unordered_map에서 count() 함수
  : 특정 key가 존재하는지 확인
  • key가 존재하면 1을, 존재하지 않으면 0을 반환
  • find()와의 차이: find()는 key가 존재하면 iterator를, 존재하지 않으면 end()를 반환
    
    
• 문자열을 회전할 때 문자열 자체를 바꾸는 게 아니라, 시작 위치를 가리키는 인덱스만 옮겨가면서 회전을 구현할 수 있음

프로그래머스 - 짝 지어 제거하기

오답

#include <iostream>
#include <string>
#include <stack>
using namespace std;

int solution(string s)
{
    int answer = -1;
    stack<char> stk;
    
    for (int i = 0; i < s.length(); i++) { 
        stk.push(s[i]);
        
        if (stk.top() == s[i + 1] % s.length()) {
            stk.pop();
            i++;    
        }
    }

    return stk.empty();
}

💭 풀이
s[i]에 해당하는 문자를 stack에 넣고, 다음 인덱스 문자와 비교하여 같으면 pop하고 다다음 문자열로 넘어감

💥 문제점
일단 무조건 s[i]를 push하고 스택을 검사하기 때문에 나중에 짝이 나오는 경우 처리를 못 함

✅ 해결
문자열이 비어있거나, stack의 top이 현재 가리키는 문자열과 같지 않을 때만 push

정답

#include <iostream>
#include <string>
#include <stack>
using namespace std;

int solution(string s)
{
    int answer = -1;
    stack<char> stk;
    
    for (int i = 0; i < s.length(); i++) { 
        if (stk.empty() || stk.top() != s[i]) {
            stk.push(s[i]);
        }
        else {
            stk.pop();
        }
    }

    return stk.empty();
}