2166. Design Bitset / TypeScript

class Bitset {
  private default = 0;
  private different = new Set<number>();

  constructor(private size: number) {}

  fix(idx: number): void {
    this.different[this.default ? "delete" : "add"](idx);
  }

  unfix(idx: number): void {
    this.different[this.default ? "add" : "delete"](idx);
  }

  flip(): void {
    this.default = +!this.default;
  }

  all(): boolean {
    return this.count() === this.size;
  }

  one(): boolean {
    return this.count() > 0;
  }

  count(): number {
    return this.default ? this.size - this.different.size : this.different.size;
  }

  toString(): string {
    let str = "";
    for (let i = 0; i < this.size; i++) {
      str += this.different.has(i) ? +!this.default : this.default;
    }
    return str;
  }
}

A Bitset is a data structure that compactly stores bits.

Implement the Bitset class:

• Bitset(int size) Initializes the Bitset with size bits, all of which are 0.
• void fix(int idx) Updates the value of the bit at the index idx to 1. If the value was already 1, no change occurs.
• void unfix(int idx) Updates the value of the bit at the index idx to 0. If the value was already 0, no change occurs.
• void flip() Flips the values of each bit in the Bitset. In other words, all bits with value 0 will now have value 1 and vice versa.
• boolean all() Checks if the value of each bit in the Bitset is 1. Returns true if it satisfies the condition, false otherwise.
• boolean one() Checks if there is at least one bit in the Bitset with value 1. Returns true if it satisfies the condition, false otherwise.
• int count() Returns the total number of bits in the Bitset which have value 1.
• String toString() Returns the current composition of the Bitset. Note that in the resultant string, the character at the ith index should coincide with the value at the ith bit of the Bitset.

 

Example 1:

Input
["Bitset", "fix", "fix", "flip", "all", "unfix", "flip", "one", "unfix", "count", "toString"]
[[5], [3], [1], [], [], [0], [], [], [0], [], []]
Output
[null, null, null, null, false, null, null, true, null, 2, "01010"]

Explanation
Bitset bs = new Bitset(5); // bitset = "00000".
bs.fix(3);     // the value at idx = 3 is updated to 1, so bitset = "00010".
bs.fix(1);     // the value at idx = 1 is updated to 1, so bitset = "01010". 
bs.flip();     // the value of each bit is flipped, so bitset = "10101". 
bs.all();      // return False, as not all values of the bitset are 1.
bs.unfix(0);   // the value at idx = 0 is updated to 0, so bitset = "00101".
bs.flip();     // the value of each bit is flipped, so bitset = "11010". 
bs.one();      // return True, as there is at least 1 index with value 1.
bs.unfix(0);   // the value at idx = 0 is updated to 0, so bitset = "01010".
bs.count();    // return 2, as there are 2 bits with value 1.
bs.toString(); // return "01010", which is the composition of bitset.

 

출처 : https://leetcode.com/problems/design-bitset/description/

 

 

풀이 

class Bitset {
  private default = 0;
  private different = new Set<number>();

  constructor(private size: number) {}

  fix(idx: number): void {
    this.different[this.default ? "delete" : "add"](idx);
  }

  unfix(idx: number): void {
    this.different[this.default ? "add" : "delete"](idx);
  }

  flip(): void {
    this.default = +!this.default;
  }

  all(): boolean {
    return this.count() === this.size;
  }

  one(): boolean {
    return this.count() > 0;
  }

  count(): number {
    return this.default ? this.size - this.different.size : this.different.size;
  }

  toString(): string {
    let str = "";
    for (let i = 0; i < this.size; i++) {
      str += this.different.has(i) ? +!this.default : this.default;
    }
    return str;
  }
}

 

 

클래스 구성 요소

1. default: 초기 값으로 모든 비트를 0으로 설정하고 시작하며, flip 메서드를 호출하면 1로 설정됨
   1. 현재 비트들의 기본값을 나타내는 변수
2. different: 기본값과 다른 상태(즉, default 값이 0일 때 1, 1일 때 0)를 가진 인덱스를 저장하는 Set<number> 자료구조.
   1. 기본적으로 모든 비트는 default 값과 동일하다고 가정하고, 기본값과 다른 인덱스만 이 Set에 저장.
3. size: 비트셋의 크기.

메서드 설명

• fix(idx: number): 특정 인덱스의 비트를 1로 고정.
  • 현재 default 값에 따라 default가 0이면 해당 인덱스를 different에 추가하고, default가 1이면 해당 인덱스를 different에서 제거
  • 이는 해당 인덱스가 1이 되도록 만드는 역할을 함
• unfix(idx: number): 특정 인덱스의 비트를 0으로 해제.
  • default 값에 따라 default가 1이면 해당 인덱스를 different에 추가하고, default가 0이면 해당 인덱스를 different에서 제거
  • 이는 해당 인덱스가 0이 되도록 만듬.
• flip(): 모든 비트의 값을 뒤집음.
  • 현재 default 값을 0에서 1로 또는 1에서 0으로 전환
  • !this.default는 !0으로 계산. 논리적으로 0은 false로 취급되므로, !0은 true.
  • +!this.default는 +true로 계산. true는 숫자로 변환하면 1.
  • 따라서, this.default는 1로 업데이트
• all(): 모든 비트가 1인지 확인하는 메서드.
  • 현재 1로 설정된 비트의 수가 전체 비트셋의 크기와 동일한지 여부를 반환.
• one(): 하나 이상의 비트가 1인지 확인하는 메서드.
  • 1로 설정된 비트가 하나 이상 있으면 true, 없으면 false를 반환.
• count(): 현재 1로 설정된 비트의 개수를 반환.
  • default 값에 따라 전체 비트셋 크기에서 different에 포함된 인덱스 수를 빼거나, different에 포함된 인덱스 수를 그대로 반환
  • toString(): 현재 비트셋의 상태를 문자열로 반환. 각 비트를 순회하며, 해당 인덱스가 different에 포함되어 있는지와 default 값을 기준으로 문자열을 구성.

 

Input:
["Bitset", "fix", "fix", "flip", "all", "unfix", "flip", "one", "unfix", "count", "toString"]
[[5], [3], [1], [], [], [0], [], [], [0], [], []]

1. Bitset(5) -> 비트셋 크기가 5인 객체를 생성.
   초기 상태: default = 0, different = []

2. fix(3) -> 인덱스 3의 비트를 1로 고정.
   상태: default = 0, different = [3]

3. fix(1) -> 인덱스 1의 비트를 1로 고정.
   상태: default = 0, different = [1, 3]

4. flip() -> 모든 비트 값을 뒤집음.
   상태: default = 1, different = [1, 3]
   이제 기본값이 1이 되고, `different`에 있는 인덱스는 0으로 간주됨.

5. all() -> 모든 비트가 1인지 확인
   현재 `different`에 두 개의 인덱스가 있으므로, 전체 비트셋이 모두 `1`이 아님. 결과는 `false`.

6. unfix(0) -> 인덱스 0의 비트를 0으로 해제.
   상태: default = 1, different = [0, 1, 3]
   이제 인덱스 0이 `different`에 추가되어 0으로 설정.

7. flip() -> 모든 비트 값을 다시 뒤집음.
   상태: default = 0, different = [0, 1, 3]
   이제 기본값이 다시 0으로 돌아오고, `different`에 있는 인덱스는 1로 간주.

8. one() -> 하나 이상의 비트가 1인지 확인.
   `different`에 포함된 인덱스가 있으므로 결과는 `true`.

9. unfix(0) -> 인덱스 0의 비트를 0으로 해제.
   상태: default = 0, different = [1, 3]
   이제 인덱스 0은 0으로 설정되어, `different`에서 제거.

10. count() -> 현재 1로 설정된 비트의 개수를 반환.
    `different`에 포함된 인덱스가 2개 있으므로 결과는 `2`.

11. toString() -> 현재 비트셋의 상태를 문자열로 반환.
    상태는 `"01010"`.