[팬미팅] c++ bitset으로 모든경우 탐색하는데 오답 원인을 모르겠습니다.

  • MKRO
    MKRO

    문제 링크입니다.
    https://www.algospot.com/judge/problem/read/FANMEETING

    C++ bitset을 이용하는데 오답 원인을 모르겠어서 질문드립니다..
    틀린 부분이나 오답을 낼 수 있는 테스트 케이스를 알려 주시면 감사하겠습니다.ㅜ

    아래의 내용은 순서대로
    알고리즘 설명,
    c++ 소스코드,
    제가 테스트하는 테스트케이스 입니다.


    알고리즘 설명

    1. 가수와 팬을 bitset으로 표현할 각각 크기 20000의 bitset을 만들고
    2. 남성은 1, 여성은 0 으로 표현한다. 순서는 가장 오른쪽 사람이 LSB에 들어가도록 한다.(즉 문제는 팬이 가장 왼쪽 사람부터 들어가지만 풀이에서는 팬이 가장 오른쪽 사람 부터 들어가게됨 그런데 이 순서는 상관이 없음)
    3. 두 bitset을 AND 연산했을 때, 결과가 0이 아니면 어딘가에서 남성 가수와 남성 팬이 만난 경우이다.
    4. 두 bitset을 AND 연산했을 때, 결과가 0이면 남성 가수와 남성 팬이 만나지 않은 경우 이므로 결과 값에 1을 더한다.
    5. 3,4번을 반복하면서 매번 반복마다 팬 bitset을 오른쪽 한칸 시프트연산한다.
    6. 이때 반복 횟수는 가수 중 팬과 마주하지 않는 가수가 없도록하는 모든 상황 즉, [팬의 수 - 가수의 수 + 1] 이다.
    7. 결과 값을 리턴한다.
    8. [예외상황1]가수가 모두 여자이거나 팬이 모두 여자면 모든 상황에서 전부 포옹하므로 [팬의 수 - 가수의 수 + 1]를 리턴한다.
    9. [예외상황2]팬이 전부 남자고 가수 중 남자가 하나라도 있으면 전부 포옹할 수 있는 상황이 없으므로 0을 리턴한다.


    c++ 소스코드

    #include <iostream>
#include <bitset>

void makeBitsetFor(const std::string& input, std::bitset<20000>* bitset) {
    for(auto& c : input) {
        (*bitset)<<=1;
        if(c=='M')
            bitset->set(0);
    }
}

int solution(const std::string& singerInput, const std::string& fanInput) {
    auto singers = std::bitset<20000>(0);
    auto fans = std::bitset<20000>(0);

    makeBitsetFor(singerInput, &singers);
    makeBitsetFor(fanInput, &fans);

    /* 사인 해야 하는 총 횟수*/
    int fanSize = fanInput.size();
    int numSign = fanSize - singerInput.size() + 1;

    /* 싱어가 다 여자거나 팬이 다 여자면 모든 횟수에서 쌉가능*/
    if(singers.none() || fans.none())
        return numSign;

    /* 팬이 다 남자고 가수중에 남자가 하나라도 있으면 절대 불가 */
    if(fans.count() == fanSize && singers.any())
        return 0;

    int ret = 0;
    while(numSign-- != 0) {
        /*AND 연산 결과가 0 이면 남-남 만나지 않은 것*/
        if((singers&fans).none())
            ret += 1;
        fans >>= 1;
    }

    return ret;
}

#ifndef TEST_BUILD
int main(int argc, const char *argv[])
{
    int testCase;
    std::cin >> testCase;

    while(testCase-- != 0) {
        std::string singer;
        std::string fan;
        std::cin >> singer;
        std::cin >> fan;
        std::cout <<solution(singer, fan)<< std::endl;
    }

    return 0;
}
#endif


    테스트 케이스

    • 아래의 테스트케이스에 추가로 다음 세개 케이스가 있습니다.
    • 2만 명의 가수가 모두 남자이고 2만 명의 팬은 남,여가 섞인 경우 = 0
    • 2만 명의 가수가 모두 여자고 2만 명의 팬은 남,여가 섞인 경우 = 1
    • 2만 명의 가수가 남, 여가 섞이고 2만 명의 팬은 모두 여자인 경우 = 1
    TEST(solution_test, default_ex_1) {
    std::string sin_input = "FFFMMM";
    std::string fan_input = "MMMFFF";
    int result = 1;
    int answer = solution(sin_input, fan_input);

    ASSERT_EQ(result, answer);
}

TEST(solution_test, default_ex_2) {
    std::string sin_input = "FFFFF";
    std::string fan_input = "FFFFFFFFFF";
    int result = 6;
    int answer = solution(sin_input, fan_input);

    ASSERT_EQ(result, answer);
}

TEST(solution_test, default_ex_3) {
    std::string sin_input =      "FFFFM";
    std::string fan_input = "FFFFFMMMMF";
    int result = 2;
    int answer = solution(sin_input, fan_input);

    ASSERT_EQ(result, answer);
}

TEST(solution_test, default_ex_4) {
    std::string sin_input =                         "MFMFMFFFMMMFMF";
    std::string fan_input = "MMFFFFFMFFFMFFFFFFMFFFMFFFFMFMMFFFFFFF";
    int result = 2;
    int answer = solution(sin_input, fan_input);

    ASSERT_EQ(result, answer);
}

TEST(solution_test, ex_5) {
    std::string sin_input = "FFFFFFFFFFFFFF";
    std::string fan_input = "MMFFFFFMFFFMFFFFF";
    int result = 4;
    int answer = solution(sin_input, fan_input);

    ASSERT_EQ(result, answer);
}

TEST(solution_test, ex_6) {
    std::string sin_input = "FFFFFFFFFFFFMF";
    std::string fan_input = "FFFFFFFFFFFFFFFFF";
    int result = 4;
    int answer = solution(sin_input, fan_input);

    ASSERT_EQ(result, answer);
}

TEST(solution_test, ex_7) {
    std::string sin_input =    "FFFFFFFFFFFFMF";
    std::string fan_input = "MMMMMMMMMMMMMMMMM";
    int result = 0;
    int answer = solution(sin_input, fan_input);

    ASSERT_EQ(result, answer);
}

TEST(solution_test, ex_8) {
    std::string sin_input =   "MMMMMMMMMMMMMM";
    std::string fan_input ="FFFFFFFFFFFFFFFFM";
    int result = 3;
    int answer = solution(sin_input, fan_input);

    ASSERT_EQ(result, answer);
}

TEST(solution_test, ex_9) {
    std::string sin_input ="M";
    std::string fan_input ="M";
    int result = 0;
    int answer = solution(sin_input, fan_input);

    ASSERT_EQ(result, answer);
}

    4년 전
2개의 댓글이 있습니다.
  • dbfldkfdbgml
    dbfldkfdbgml

    다 되는 소스입니다.

    20000을 200000
    이만을 이십만으로 고치세요. 됩니다.


    4년 전 link
  • MKRO
    MKRO

    감사합니다!!


    4년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.