2020 카카오 신입 개발자 블라인드 채용 1차 코딩 테스트 2번


작성일 : 2019-12-10 02:02:17
조회수 : 152



본문

2번부터는 바로 포스팅을 시작하도록 하겠습니다.


문제는 굉장히 길고 복잡해 보이지만 이런 문제는 주로 규칙대로 구현만 하면 쉽게 풀리는 유형의 문제들입니다. 핵심은 전체 문자열에서 $($ 와 $)$ 의 개수가 맞는 균형잡힌 괄호 문자열을 먼저 찾은 다음, 나머지 문자열에 대해 재귀함수를 실행하면서 최종적으로 규칙 1번 '빈 문자열 반환' 까지 처리해 주면 되는 문제입니다.


이런 문제는 머리로 괄호를 붙여보면 오히려 더 어렵습니다. 하라는대로 하면 됩니다. 다만 이 문제에서도 주의해야 할 용어가 있는데, 나머지 문자열의 괄호 방향을 뒤집으란 얘기는 문자열을 reverse하라는 것이 아닌, $($ 를 $)$로, $)$ 를 $($ 로 뒤집어준다는 의미입니다. 이를 헷갈리게 하려고 의도한 것인지 )(를 뒤집어 ()가 되는 것을 예로 들어 최초 채점에서 틀렸었습니다.


요 부분만 주의한다면 문자열의 길이가 1000 이하이므로 특별히 큰 최적화가 필요 없이 문제를 구현하는대로 풀 수 있게 됩니다. 소스는 클릭하여 보기를 통해 확인 가능합니다.

#include <string>
#include <vector>
#include <iostream>

using namespace std;

string dfs(string s) {
    if (s == "") return "";
    int idx = 0, sum = 0;
    bool invalid = false;
    string ret = "";
    while (idx < s.length()) {
        ret += s[idx];
        sum += s[idx] == '(' ? 1 : -1;
        if (sum < 0) invalid = true;
        if (sum == 0) break;
        idx++;
    }
    string rem = "";
    if (idx + 1 < s.length()) {
        rem = s.substr(idx + 1, s.length() - idx - 1);    
    }
    if (!invalid) {
        ret += dfs(rem);
    }
    else {
        string tmp = "(" + dfs(rem) + ")", tmp2 = "";
        if (ret.length() > 0) ret.erase(0, 1);
        if (ret.length() > 0) ret.pop_back();
        for (char c : ret) {
            tmp2 += c == '(' ? ')' : '(';
        }
        tmp += tmp2;
        ret = tmp;
    }
    return ret;
}

string solution(string p) {
    return dfs(p);
}

2020 카카오 신입 개발자 블라인드 채용 1차 코딩 테스트 2번 - 알고리즘닷컴
취업 대비 알고리즘에서는 다양한 기업들의 기출 문제 및 경향, 풀이 등에 대한 포스팅을 다룹니다.