[팬미팅] 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);
    }
    

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

    다 되는 소스입니다.

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


    2달 전 link
  • MKRO
    MKRO

    감사합니다!!


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