[프로그래머스] 괄호 변환 / substr

문제

 

풀이

#include <string>
#include <vector>
#include <stack>
using namespace std;
bool check(string p);
//괄호는 stack으로 해결

string solution(string p) {
    string answer = "";
    string u, v;
    int count = 0;
    
    if(p.size() == 0) return "";
    
    for(int i=0; i<p.size(); i++){
        if(p[i] == '('){
            count+=1;
        }
        else if( p[i] ==')'){
            count-=1;
        }
        
        if(count == 0){
            u = p.substr(0, i+1); 
            v = p.substr(i+1, p.size()-i);
            break;
        }
    }
    if(check(u)){
        return u + solution(v);
    }
    u = u.substr(1, u.size()-2);
    for(int i=0; i<u.size(); i++){
        if(u[i] == '(') u[i] = ')';
        else u[i] = '(';
    }
    return "(" + solution(v) + ")" + u;
}

bool check(string p){
    stack<int> s;
    for (int i = 0; i < p.size(); i++) {
		if (p[i] == '(') { s.push(p[i]);
		}
		else if( p[i] ==')'){
            if(s.empty()) return false;
			if (s.top() == '(') s.pop();
		}
	}
    
    return s.empty()?true:false;
}

알고리즘은 문제에 정리된 순서대로 구현했다.

check함수를 만들어 문자열이 올바른 괄호 문자열인지 확인하도록 했다.

올바른 괄호 문자열인지 확인하기 위해 stack구조를 활용했다.

 

 

 

substr

문자열의 부분 문자열을 리턴한다.

substr(pos, count)

• pos : 첫번째 문자의 위치
• count : 부분 문자열의 길이

원래 문자열에서 [pos, pos + count) 까지의 문자열을 반환한다.

pos 가 원래 문자열의 길이보다 길다면 std::out_of_range 예외를 발생시킨다.

 

 

 

---

 

다른 사람 풀이

#include <bits/stdc++.h>
using namespace std;

bool check(const string &a) {
    int r = 0;
    for (char ch : a) {
        if (ch == '(') ++r;
        else --r;
        if (r < 0) return false;
    }
    return r == 0;
}
string solution(string p) {
    if (p == "") return "";
    if (check(p)) return p;

    int i, t = 0;
    for (i = 0; i < p.size(); ++i) {
        if (p[i] == '(') ++t;
        else --t;
        if (t == 0) break;
    }

    string u = p.substr(0, i + 1);
    string v = p.substr(i + 1);

    if (check(u)) return u + solution(v);

    for (char &ch : u) ch = ch == '(' ? ')' : '(';
    return string("(") + solution(v) + ")" + u.substr(1, u.size() - 2);
}

나와 다른 점은 올바른 괄호 문자열을 확인하는데 stack을 활용하지 않은 것과, 코드가 더 간결하다는 점이다!

 

 

 

---

https://modoocode.com/235

C++ 레퍼런스 - string 의 substr 함수