[Jungol] 정올 3292 집합관리

출처: http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=2582&sca=99&page=22

Approach

0 ~ 31까지의 중복되지 않는 원소로 이루어진 집합이므로

231 Bit 연산으로 구합니다. (unsigned int 이용)

※ 비트마스크 (Bitmask) 

비트마스크 (Bitmask)

 

void Init() ▶ M = 0;

- 각 테스트 케이스에 대하여 1번 호출되며, 집합을 공집합으로 만든다.

- 변수의 값을 0으로 초기화

 

void Flip() ▶ M = ~M;

- 집합에 포함된 모든 원소들을 삭제하고 기존에 없었던 원소들을 추가한다.

- 각 자리 비트를 반전시킵니다.

 

void Insert(int k) ▶ M |= (1 << k);

- 집합에 원소 k가 없다면 추가, 있다면 아무일도 하지 않는다.

- 특정 위치를 "1"로 바꾸기 → 해당 위치(k)에 1을 위치 시키고 (1 << k) OR연산( | )

 

void Erase(int k) ▶ M &= ~(1 << k);

- 집합에 원소 k가 있다면 삭제, 없다면 아무일도 하지 않는다.

- 특정 위치를 0으로 바꾸기→ 해당 위치(k)에 0, 다른 위치는 1로 채웁니다.

  (~(1 << k)): 0으로 위치할 자리로 이동시키고 Bit를 반전시킨 후 AND연산(&)

 

int Find(int k) ▶ return (M >> k) & 1;

- 집합에 원소 k가 집합안에 있다면 1, 없다면 0 반환

- 값을 바꾸는 것이 아니므로 return으로 반환만 합니다.

- k번 원소를 맨 오른쪽으로 보내고: M >> k

  가장 오른쪽 1의 자리 Bit가 0인지 1인지 AND 연산(&)

 

 

void Inverse(int k) ▶ M ^= (1 << k);

- 집합에 원소 k가 없다면 추가, 있다면 삭제한다.

- 1을 k위치에 이동(shift)한 후, XOR연산 (^)

   (^0 = 원래의 값, ^1 = 반전된 값)

 

void Plus(int k) ▶ M = (M << k) | (M >> (32 - k));

- 집합에 모든 원소를 삭제하고 기존 원소에 k를 더한 원소들로 채운다.

  k를 더한 원소가 31을 초과하는 경우 32로 나눈 나머지를 새로운 원소로 한다.

  ex) 8 + 3 = 11 ↔ 10002 + 112 = 10112

- (초과하는 것을 고려하지 않을 때) k를 더하는 것은 기존 M에서 은 k만틈 Left Shift 연산(<<) → (M << k)

- 하지만 31을 초과하는 경우에는 32로 나눈 나머지로 처리해야 합니다.

  이를 위해서 31을 초과하는 값들만 추출해서 K만큼 더해서 32로 나눈 나머지를 구하여야 하는데

  결과적으로는 기존 M을 (32 - k)만큼 Right Shfit(>>) 해주면 동일한 결과를 얻을 수 있습니다. → (M >> (32 - k))

- 와 를 더하기 혹은 OR 연산 처리.

 

void Minus(int k) ▶ M = (M >> k) | (M << (32 - k));

- 집합에 모든 원소를 삭제하고 기존 원소에 k를 뺀 원소들로 채운다.

  k를 뺀 원소가 음수인 경우 32로 나눈 나머지에 32를 더한 결과를 새로운 원소로 한다.

- Plus() 함수와 다르게 Shift 연산 방향을 반대로 합니다. 

- k를 빼는 것은 k만큼 Right Shfit 연산(>>) → (M >> k)

- 음수가 나오는 것은 (32 - k)만큼 Left Shift 연산(<<) → (M << (32 - k))

- 두 연산 결과를 더하기 혹은 OR 연산 합니다. 

 

void Clear(int k) ▶ M &= ~((1 << k) - 1 | (1 << k));

- k보다 작거나 같은 원소들 중 집합에 있는 원소를 모두 삭제한다.

- k 이하 위치에는 0, k 초과 위치에는 1로 채운 후 AND 연산(&) 하면 됩니다.

  ex) Bit 자리가 210  이며, k =7인 경우: 1 1 1 0 0 0 0 0 0 0

- (1 << k) - 1  ex) (1 << 4) - 1 = 0 1 1 1 → K 위치는 "0" 하위 Bit는 "1"    

- (1 << k)  ex) 1<<4 = 1 0 0 0 → K 위치 "1"

- (((1 << k) - 1) | (1 << k)): 같은 원소를 포함하여 하위 Bit를 "1"로 표시하여 Bit 반전(~)

  ex) Bit 자리가 210  이며, k =7인 경우: 0 0 0 1 1 1 1 1 1 1 → 1 1 1 0 0 0 0 0 0 0

  if) "(1 << (k + 1)) - 1" 수식으로도 "k 위치까지 1로 표시하기" 가능해보이지만,

      k = 31과 같이 31 + 1 만큼 shift 한다면 정해진 자릿수를 벗어납니다.

      이러한 경우를 컴파일러마다 쓰레기값으로 처리하는 등 처리하는 방식이 다르기 때문에

      범위를 벗어나는 연산의 경우 예외처리를 하거나 long long 이용하여야 합니다.

 

void Fill(int k) ▶ M |= (((1 << k) - 1) | (1 << k));

- k보다 작거나 같은 원소들 중 집합에 없는 원소를 추가한다.

- OR 연산(|)은 더해주는 효과가 있습니다.

  ex) 1 0 1 0 + 0 1 0 1 = 1 1 1 1

- (1 << k) - 1  ex) (1 << 4) - 1 = 0 1 1 1 → K 위치는 "0" 하위 Bit는 "1"    

- (1 << k)  ex) 1<<4 = 1 0 0 0 → K 위치 "1"

- (((1 << k) - 1) | (1 << k)): 같은 원소를 포함하여 하위 Bit를 "1"로 표시한 후 OR연산 ( | ) 

---

unsigned int M;

/// 각 테스트 케이스에 대하여 1번 호출된다. 집합을 공집합으로 만든다.
void Init() {
    M = 0;
}

/// 집합에 포함된 모든 원소들을 삭제하고 기존에 없었던 원소들을 추가한다.
void Flip() {
    M = ~M;
}

/// 집합에 원소 k가 없다면 추가, 있다면 아무일도 하지 않는다.
void Insert(int k) {
    M |= (1 << k);
}

/// 집합에 원소 k가 있다면 삭제, 없다면 아무일도 하지 않는다.
void Erase(int k) {
    M &= ~(1 << k);
}

/// 집합에 원소 k가 집합안에 있다면 1, 없다면 0을 반환한다.
int Find(int k) {
    return (M >> k) & 1;
}

/// 집합에 원소 k가 없다면 추가, 있다면 삭제한다.
void Inverse(int k) {
    M ^= (1 << k);
}

/// 집합에 모든 원소를 삭제하고 기존 원소에 k를 더한 원소들로 채운다.
/// k를 더한 원소가 31을 초과하는 경우 32로 나눈 나머지를 새로운 원소로 한다.
void Plus(int k) {
    M = (M << k) | (M >> (32 - k));
}

/// 집합에 모든 원소를 삭제하고 기존 원소에 k를 뺀 원소들로 채운다.
/// k를 뺀 원소가 음수인 경우 32로 나눈 나머지에 32를 더한 결과를 새로운 원소로 한다.
void Minus(int k) {
    M = (M >> k) | (M << (32 - k));
}

/// k보다 작거나 같은 원소들 중 집합에 있는 원소를 모두 삭제한다.
void Clear(int k) {
    M &= ~((1 << k) - 1 | (1 << k));
}

/// k보다 작거나 같은 원소들 중 집합에 없는 원소를 추가한다.
void Fill(int k) {
    M |= (((1 << k) - 1) | (1 << k));
}