2020 카카오 신입사원 코딩테스트 - 괄호 변환

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

코딩테스트 연습 - 괄호 변환 | 프로그래머스

 

 

이번 문제는 설명한 대로 구현할 수 있는지에 대한 문제입니다.

그런데 저처럼 '읽기 능력이 현저히 떨어지시는 분들' 또는 '재귀 문제가 낯선 분들'은 쉽지 않으셨을 겁니다.

 

이럴 때 팁!!

물론 알고리즘 문제를 많이 풀어보신 분들에게는 팁이라고 느껴지지는 않겠지만.

 

'예제 설명이 있다면, 예제 설명을 먼저 본다!'

 

저도 이 문제를 읽다가 명확히 이해가 가지 않아서, 바로 예제 설명으로 넘어가 이해 후 풀었습니다.

 

혹시 '재귀 함수가 너무 어렵다' 고 하신다면, 아래 글을 보시면 도움이 됩니다!

 

https://yomyom0824.tistory.com/13

재귀함수를 이용한 완전탐색의 기본에 대해서 (1)

https://yomyom0824.tistory.com/49

재귀함수를 이용한 완전탐색의 기본에 대해서 (2)

 

이 문제에서 배울 수 있는 것들이 무엇인지 알아보죠!

 

1. 올바른 괄호 문자열 검증에 대한 두 가지 방법

2. 문자열 자르는 함수 : s.substr(시작 인덱스, 몇 개의 문자를 가져올 것인지);   (코테 c++ 꿀팁 :https://yomyom0824.tistory.com/15)

 

 

 

 

1. 올바른 괄호 문자열 검증에 대한 두 가지 방법

 

https://www.acmicpc.net/problem/9012

9012번: 괄호

 

이 문제를 풀면서 알아봅시다.

 

 

 

(1) stack 사용해서 검증하기

 

stack을 사용할 때 가장 실수하기 좋은 부분!

우선 stk.pop() 또는 stk.top() 함수를 콜하기 전에 stk.empty() 로 현재 스택이 비어있는지, 아닌지 확인하는 것이 가장 중요합니다.

 

이것이 보통 stack 사용할 때,  'segmentation fault' 오류의 주범입니다

그리고 '문자열 압축' 문제에서도 언급했지만, stack 문제를 풀 때 stack에 남아있는 값에 대한 처리가 필요한지에 대해서

생각해 보는 것이 중요합니다. 

 

이 문제에서 input으로 '(((' 가 들어올 경우, 곧 설명할 알고리즘으로 걸러낼 수 없습니다. 

for문이 다 끝나고  stack에 짝이 맞춰지지 않은 괄호가 남아 있는지 확인해야 합니다.

 

알고리즘

1. '(' 이라면 stack에 push 한다.

2. ')' 이라면 stack이 비어있는지 확인한다.

3. stack이 비어있거나, '(' 이 아니라면 현재 ')' 과 맞는 짝이 없으므로 올바른 괄호 문자열이 아니다. 바로 break로 끝낸다.

4. stack.top() 을 확인해, '(' 이라면 pop 한다.

 

#include <iostream>
#include <vector>
#include <string>
#include <stack>
 
using  namespace std;
 
 
int main(){
    int t;
    cin >> t;
    while(t--) {
        stack<char> stk;
        string s;
        cin >> s;
        
        bool isRight = true;                    // 올바른 괄호 문자열인지 기록하는 불 변수
        for(int i = 0; i < s.size(); i++){
            char c = s[i];
            if(c == '(') {
                stk.push(c);
            }
            else {
                if(!stk.empty() && stk.top() == '(') stk.pop();        // stk.top 또는 stk.pop 을 하기 전에 반드시 stk.empty 함수로 확인하는 것이 중요하다
                else {
                    isRight = false;            // 이 경우 올바른 괄호 문자열이 아니므로 false로 기록후 나간다
                    break;
                }
            }
        }
 
        if(stk.empty() && isRight) cout << "YES" << endl;    // 마지막에 스택에 남아있는 값이 있다면, 올바른 괄호 문자열이 아니므로 이를 확인해준다
        else cout << "NO" << endl;
    }
}

 

 

 

 

(2) 단순 변수를 사용해서 검증하기

 

이 방법은 한 종류의 괄호만 사용할 때 가능한 방법으로 알고 있습니다.

두 종류 이상의 괄호를 사용할 때도 단순 변수를 통해서 검사 가능한 방법을 알고 계시다면 저에게도 공유해주시면 감사드리겠습니다.

 

알고리즘

1. '(' 일 경우, balance에 1을 더한다.

2. ')'일 경우, balance에 1을 뺀다.

3. balance 값이 0 아래로 떨어졌는지 확인한다. 

4. 음수라면 올바른 괄호 문자열이 아니므로 끝낸다.

 

balance 변수 값이 음수가 될 경우 무조건 올바른 괄호 문자열이 될 가능성이 없다는 것은, 스스로 몇 개의 예제를 만들어서 확인해 

보시기 바랍니다.

 

여기서도 위 stack을 사용했던 것과 같이 for 문이 다 끝난 후, balance 값이 0 인지 확인해야 합니다.

만약 input이 '(((' 일 경우 balance 값이 3으로 끝날 텐데 이는 올바르지 않기 때문입니다.

 

따라서 모든 알고리즘이 끝난 후, balance 값이 반드시 0이어야 합니다.

 

 

#include <iostream>
#include <vector>
#include <string>
#include <stack>
 
using  namespace std;
 
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    int t;
    cin >> t;
    while(t--) {
        string s;
        cin >> s;
        
        int balance = 0;
        for(int i = 0; i < s.size(); i++){
            char c = s[i];
            if(c == '(') balance += 1;
            else balance -= 1;
 
            if(balance < 0) break;
        }
 
        if(balance == 0) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
}

 

 

 

 

 

이제 코드를 봅시다.

 

#include <string>
#include <vector>
 
using namespace std;
 
string solution(string p) {
    if(p == "") return p;
    
    string u = "", v = "";
    bool isRightString = false;    // 올바른 괄호 문자열인지 기록하는 불 변수
    int balance = 0, idx = 0;
    
 
    // 위에서 봤던 balance 변수를 통한 괄호 문자열 검증 방법
    for(; idx < p.size(); idx++){
        u += p[idx];
        
        if(p[idx] == '(') balance += 1;
        else balance -= 1;
       
        if(balance < 0) isRightString = true;
        else if(balance == 0) break;
    }
    
 
    if(idx + 1 < p.size()) v = p.substr(idx + 1);    // 문자열 p에서 조건에 맞게 u를 만든 후, 남아있는 문자열을 v에 저장한다  
    
    v = solution(v);        // 어쨌든 v는 재귀함수로 다시 처리주어야 한다
    
    if(isRightString) {
 
        // 문제에서 설명한 대로 u가 올바른 괄호 문자열이 아닐 경우의 처리
        string ret = "(" + v + ")";
        for(int i = 1; i < u.size() - 1; i++){
            if(u[i] == '(') ret += ')';
            else ret += '(';
        }
        return ret;
    }
    else {
        return u + v;   
    }
}