competitive-programming2022년 2월 11일1분 분량

[LEETCODE] 2166. Design Bitset 풀이

수정일: 2022년 2월 11일

Ad hoc

지원 언어:enko

#Problem

2166. Design Bitset

#Approach

모든 연산은 $O(1)$ 시간에 처리할 수 있습니다.

n: 크기
cnt: 1의 개수
flipped: 반전되었는지 확인 ⭐️
bitset: 비트들의 벡터 배열
orig: bitset의 to_string() 값
comp: 반전된 bitset의 to_string() 값

#`fix(idx)`:

해당 비트를 반전해야 한다면,
cnt를 1 증가시키고
bitset[idx], orig[idx], comp[idx]를 반전합니다

#`unfix(idx)`:

해당 비트를 반전해야 한다면,
cnt를 1 감소시키고
bitset[idx], orig[idx], comp[idx]를 반전합니다

#`flip()`:

cnt = n-cnt
flipped = flipped ^ 1

#`all()`:

cnt == n을 반환합니다

#`one()`:

cnt > 0을 반환합니다

#`count()`:

cnt를 반환합니다

#`toString()`:

flipped ? comp : orig을 반환합니다

#Code

/**
 * written: 2022. 02. 11. Fri. 17:41:01 [UTC+9]
 * jooncco의 mac에서.
 **/

typedef vector<int> vi;

class Bitset {
private:
    int n, cnt, flipped;
    vi bitset;
    string orig, comp;

public:
    Bitset(int size) {
        n= size;
        cnt= flipped= 0;
        bitset= vi(size,0);$
        orig= string(size,'0');
        comp= string(size,'1');
    }

    void fix(int idx) {
        // need flip ?
        if ((bitset[idx]^flipped) == 0) {
            ++cnt;
            bitset[idx] ^= 1;
            orig[idx]= (char)(((orig[idx]-'0') ^ 1) + '0');
            comp[idx]= (char)(((comp[idx]-'0') ^ 1) + '0');
        }
    }

    void unfix(int idx) {
        // need flip ?
        if ((bitset[idx]^flipped) == 1) {
            --cnt;
            bitset[idx] ^= 1;
            orig[idx]= (char)(((orig[idx]-'0') ^ 1) + '0');
            comp[idx]= (char)(((comp[idx]-'0') ^ 1) + '0');
        }
    }

    void flip() {
        cnt= n-cnt;
        flipped ^= 1;
    }

    bool all() {
        return cnt == n;
    }

    bool one() {
        return cnt > 0;
    }

    int count() {
        return cnt;
    }

    string toString() {
        return flipped ? comp : orig;
    }
};

#Complexity

Time: $O(1)$
Space: $O(size)$