알고리즘 :: 프로그래머스 :: 2020 카카오 :: 스택 :: 괄호 변환

문제

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

문제접근

• 괄호 관련 문제는 거의 무조건 Stack을 쓴다!
• 문제 하단에 진행 과정이 말로 풀어서 쓰여있는데, 이 부분을 코드로 그대로 옮기면 되는 문제다.

recursive(string 문자열) {
    if (문자열.empty()) return "";  // 조건 1
    // 조건 2: u와 v를 분리하는 과정
    u = 문자열.substr(0, idx), v = 문자열.substr(idx, 문자열.length() - idx);
    if (isRight(u)) return u + recursive(v);	// 조건 3
    else { return "(" + recursive(v) + ")" + reverse(u) }; // 조건 4
}

• 위 의사코드처럼 작성하면 끝이다.

코드

// https://programmers.co.kr/learn/courses/30/lessons/60058
#include <string>
#include <stack>
using namespace std;

bool isCorrect(string str, int* pos) {
	bool ret = true;
	int left = 0, right = 0;
	stack<char> stk;
	
	for (int i = 0; i < str.length(); ++i) {
		if (str[i] == '(') {
			left++;
			stk.push('(');
		} else {
			right++;
			if (stk.empty()) ret = false;
			else stk.pop();
		}
		if (left == right) {
			*pos = i + 1;
			return ret;
		}
	}
}

string solution(string p) {
    // 조건 1 처리.
	if (p.empty()) return "";
    // 조건 2 처리.
	int pos;
	bool check = isCorrect(p, &pos);
	string u = p.substr(0, pos), v = p.substr(pos, p.length() - pos);
	// 조건 3 처리.
	if (check) return (u + solution(v));
	// 조건 4 처리.
	string answer = "(" + solution(v) + ")";
	for (int i = 1; i < u.length() - 1; ++i)
		answer += ((u[i] == '(') ? ")" : "(");
	return answer;
}

결과