https://www.codewars.com/kata/59eb1e4a0863c7ff7e000008/cpp
이번 문제는 boolean 연산입니다.
tft, ^&와 같이, 문자열 2개가 입력으로 들어옵니다.
첫 번째 문자의 t, f는 true/false를 의미하며, 두 번째 문자는 boolean연산자 AND(&), OR(|), XOR(^)를 의미합니다.
각 true/false문자 사이에 연산자가 들어가면 t ^ f & t가 되고, 괄호에 의해서 결과가 복수 개가 나올 수 있는데, 이 중에 결과가 true가 되는 조합의 개수를 리턴해야 합니다.
위의 경우는 (t ^ f) & t) = True, (t ^ (f & t)) = True 2개가 나와서 2를 리턴하면 됩니다.
일단 조합을 찾는 것이기 때문에,
recursive 방식이 될 것은 뻔해 보입니다.
recursive 연산의 결과는 true인 경우와 false인 경우의 수를 표시할 수 있도록 struct를 다음과 같이 정의했습니다.
struct tfCount
{
int64_t tCnt = 0;
int64_t fCnt = 0;
};아래처럼 연산자를 중심으로 2개의 문자로 분리를 해서 t또는 f하나만 나올 때까지 recursive를 돌리는 방식을 고안했습니다.
아래는 그 코드입니다.
operator 문자열을 순회하며 각 위치마다 분할하도록 했습니다.
for (size_t o = 0; o < opLen; ++o)
{
char op = ops[o];
std::string lhs = s.substr(0, o+1);
std::string rhs = s.substr(o+1, len - o-1);
std::string lho = ops.substr(0, o);
std::string rho = ops.substr(o + 1, len - o - 1);
tfCount lh = count(lhs, lho, visit);
tfCount rh = count(rhs, rho, visit);아래는 recursive의 종료 코드입니다.
문자 크기가 1일 때, 즉 true/false만 들어왔을 때 처리입니다.
size_t len = s.size();
size_t opLen = ops.size();
if(len == 1)
{
bool isTrue = s == "t";
cnt.tCnt = isTrue ? 1 : 0;
cnt.fCnt = isTrue ? 0 : 1;
return cnt;
}마지막으로 실제 boolean 연산을 한 결과를 합산하는 코드를 아래처럼 구현했습니다.
if(op == '&')
{
cnt.tCnt += lh.tCnt * rh.tCnt;
cnt.fCnt += lh.tCnt * rh.fCnt;
cnt.fCnt += lh.fCnt * rh.tCnt;
cnt.fCnt += lh.fCnt * rh.fCnt;
}
else if(op == '|')
{
cnt.tCnt += lh.tCnt * rh.tCnt;
cnt.tCnt += lh.tCnt * rh.fCnt;
cnt.tCnt += lh.fCnt * rh.tCnt;
cnt.fCnt += lh.fCnt * rh.fCnt;
}
else if(op == '^')
{
cnt.fCnt += lh.tCnt * rh.tCnt;
cnt.tCnt += lh.tCnt * rh.fCnt;
cnt.tCnt += lh.fCnt * rh.tCnt;
cnt.fCnt += lh.fCnt * rh.fCnt;
}이렇게 recursive 함수를 정의하고, boolean연산에 따라서 count를 계속 업데이트 해주면 일단 정답은 찾습니다. 그러나 2번째 본 테스트에서 역시 타임아웃에 걸렸습니다.
그래서 동일 문자에 대해서는 중복 연산을 하지 않고, 문자에 대한 true/false 개수를 저장하고 있다가, 동일한 문자에 대해서는 이를 사용하도록 변경했습니다. 아래의 std::map<std::string, tfCount> &visit이 그 용도입니다. map의 키를 string으로 쓰는 걸 좋아하지는 않는데 어쩔 수 없네요.
tfCount count(const std::string &s, const std::string &ops, std::map<std::string, tfCount> &visit)
{
tfCount cnt;
std::string sum = s + ops;
if(visit.find(sum) != visit.end())
{
cnt = visit[sum];
return cnt;
}전체 코드는 아래를 참고바랍니다.
https://github.com/YongheeLee/codewars_solution/blob/main/3kyu_The_Boolean_Order.cpp
