[백준/11723] 집합 비트마스킹 풀이
(파이썬, 자바스크립트, python, js, javascript)
1. 문제
https://www.acmicpc.net/problem/11723
- add x: S에 x를 추가한다. (1 ≤ x ≤ 20) S에 x가 이미 있는 경우에는 연산을 무시한다.
- remove x: S에서 x를 제거한다. (1 ≤ x ≤ 20) S에 x가 없는 경우에는 연산을 무시한다.
- check x: S에 x가 있으면 1을, 없으면 0을 출력한다. (1 ≤ x ≤ 20)
- toggle x: S에 x가 있으면 x를 제거하고, 없으면 x를 추가한다. (1 ≤ x ≤ 20)
- all: S를 {1, 2,..., 20}으로 바꾼다.
- empty: S를 공집합으로 바꾼다.
2. 문제 풀이
이 문제는, 0~20까지 집합이 있는 걸로 가정하기 때문에, 비트연산을 이용하여 풀 수 있다.
먼저 21개의 비트를 추가한다. (0~20) [ 000000000000000000010 ]
N번째 비트가 1이면 그 값이 있는 것이고, 0이면 그 값이 없는 것으로 판단해서 풀면 된다.
위 예시의 경우는 1번째 비트가 1이므로 1이 현재 집합에 있다고 볼 수 있다.
1. 초기화
bit = 0초기값을 0으로 세팅해 준다.
2. all, empty 연산
- all: S를 {1, 2,..., 20}으로 바꾼다.
- empty: S를 공집합으로 바꾼다.
if option == 'all': # * 1부터 20까지의 자리에 1을 넣어준다.
bit = 0b111111111111111111111 # 21개의 1, 0번째도 있는걸로 침
elif option == 'empty': # * S를 공집합으로 바꾼다.
bit = 0b0
'0b숫자'는 2진수를 선언할 때 사용하는 문법이다. (js, python 동일)
- all의 경우는 1~20까지 비트가 있는 걸로 선언해야 하기 때문에 0b111111111111111111111로 초기화해 준다
- empty의 경우는 공집합(모두 비어있음)으로 선언하는 것이기 때문에, 0b0으로 초기화해 준다.
3. 추가연산 (add)
- add x : S에 x를 추가한다. (1 ≤ x ≤ 20) S에 x가 이미 있는 경우에는 연산을 무시한다.
elif option == 'add': # *s에 x를 추가한다. (이미 있다면 무시 )
bit = bit | (1 << int(arr[1])) # 100번째로 이동시켜서 해당 번째 or 연산으로 추가OR연산 (|)을 이용한다.
OR연산은 1이 하나라도 있으면 1이 되기 때문에,
현재 비트가 1000인데, 만약 2번째 비트에 값을 추가한다고 치면, 1 << 2를 하면 100이 될 것이고,
1000 | 100을 진행하면, 1100이 된다.
4. 삭제 연산 (remove)
- remove x: S에서 x를 제거한다. (1 ≤ x ≤ 20) S에 x가 없는 경우에는 연산을 무시한다.
elif option == 'remove' : #S에서 x를 제거한다.
remove = ~(1<< int(arr[1])) # not연산으로 11011 삭제할것만 이럿게 만듬 그리고 and로 삭제할부분은 확실히 0으로 만들어준다
bit = bit & remove # X번째를 000 이렇게 만들어줘서 삭제하면 되지 않을까?AND연산(&)과 NOT(~) 연산을 이용한다.
AND연산은 0이 하나라도 있으면 0이 되기 때문에, 삭제할 때 사용하는 것에 적합하다.
NOT연산은 1 -> 0, 0 ->1과 같이 비트 값을 뒤집는 것이다.
※ 예시
현재 비트가 1100인데, 만약 2번째 비트의 값을 삭제한다고 치자.
1. 삭제할 비트를 우선 생성해 준다.
1 << 2를 하면 100이 될 것이고,
~(1<<2)를 하면 011이 될 것이다. (not연산을 이용해서 비트를 뒤집어준 것)
2. and 연산을 진행한다.
1100 & 1011을 진행하면, 1000이 된다. 즉 2번째 비트의 값이 삭제되는 것이다.
| 참고로, 011에서 1011이 되는 이유는 : Python에서 1 << 2는 0 b100 = 4지만, 연산 시 앞의 0이 생략되었을 뿐이고, 실제로는 무제한 비트로 동작한다 (000... 000100)
N번째 값을 0으로 두어 AND를 진행하면, 항상 N번째 값은 0이 되는 것이다.
나머지 값들은 1이기 때문에, 1이면 여전히 1이고, 0이면 여전히 0으로 남게 되기 때문에 원하는 N번째의 값만 삭제가 가능하다.
5. 토글 연산 (toggle)
- toggle x: S에 x가 있으면 x를 제거하고, 없으면 x를 추가한다. (1 ≤ x ≤ 20)
elif option == 'toggle': # * toggle x: S에 x가 있으면 x를 제거하고, 없으면 x를 추가한다. (1 ≤ x ≤ 20) xor 연산 (1->0 0->1)
bit = bit ^ (1 << int(arr[1])) # 0 1-> 1 , 1 1-> 0XOR연산(^)을 이용한다.
XOR연산은 두 값이 다르면 1이 되고, 같으면 0이 되기 때문에, N번째 값과 1로 XOR를 진행하면 된다.
- 1 -> 0 : n번째에 0이므로(없으므로) xor 연산으로 1로 만든다.(추가한다)
- 1 -> 1 : n번째에 1이므로(있으므로) xor 연산으로 0으로 만든다.(제거한다)
※ 예시
현재 비트가 1100인데, 만약 2번째 비트의 값을 toggle 한다고한다고 치자.
1. 삭제할 비트를 우선 생성해 준다.
1 << 2를 하면 100이 될 것이다.
2. xor연산을 진행한다.
1100 ^ 0100 을 진행하면, 1000이 된다. 즉 2번째 비트의 값이 이미 있기 때문에 제거되는 것이다.
5. 확인 연산 (check)
- check x: S에 x가 있으면 1을, 없으면 0을 출력한다. (1 ≤ x ≤ 20)
elif option == 'check': # * check x: S에 x가 있으면 1을, 없으면 0을 출력한다. (1 ≤ x ≤ 20)
check = (1 << int(arr[1])) # 10000 이렇게해서 값이 1이면 1, 0이면 9 출력
if bit & check: # '1'만 남아있으면 1이 맞으므로 print(1)
print(1)
else: # '0'만 남아있으면 0이므로 0
print(0)AND연산(&)을 이용한다.
1과 n번째 값을 and연산을 진행해서, 값이 있다면 1 -> 1이 되어 1이 나올 것이고,
없다면 1-> 0이 되어 0이 나올 것이다. 이렇게 확인해서 답을 출력해 준다.
※ 예시
현재 비트가 1100인데, 만약 2번째 비트의 값을 check한다고 치자.
1. 삭제할 비트를 우선 생성해준다.
1 << 2를 하면 100이 될 것이다.
2. and연산을 진행한다.
1100 & 01000100을진행하면, 100이 된다. 즉 값이 있기 때문에 if문은 true가 되는 것이다.
만약 1000 & 0100이었다면, 0000이 되어서 false로 if문에 걸렸을 것이다.
3. 코드
3-1. 파이썬 코드 (Python)
from sys import stdin
M = int(stdin.readline()) # 수행해야하는 연산 수
# S = set()
bit = 0
# 원소 S 에 num을 추가한다. S의 num번 bit만 1을 만들주면 된다.
# (1 << num)은 num번째를 1로 세팅해주는 거
for _ in range(M):
arr = list(stdin.readline().split())
option = arr[0].rstrip()
if option == 'all': # * 1부터 20까지의 자리에 1을 넣어준다.
bit = 0b111111111111111111111 # 21개의 1, 0번째도 있는걸로 침
elif option == 'empty': # * S를 공집합으로 바꾼다.
bit = 0b0
elif option == 'add': # *s에 x를 추가한다. (이미 있다면 무시 )
bit = bit | (1 << int(arr[1])) # 100번째로 이동시켜서 해당 번째 or 연산으로 추가
elif option == 'remove' : #S에서 x를 제거한다.
remove = ~(1<< int(arr[1])) # not연산으로 11011 삭제할것만 이럿게 만듬 그리고 and로 삭제할부분은 확실히 0으로 만들어준다
print(bin(1<< int(arr[1])))
print(bin(remove))
bit = bit & remove # X번째를 000 이렇게 만들어줘서 삭제하면 되지 않을까?
elif option == 'toggle': # * toggle x: S에 x가 있으면 x를 제거하고, 없으면 x를 추가한다. (1 ≤ x ≤ 20) xor 연산 (1->0 0->1)
bit = bit ^ (1 << int(arr[1])) # 0 1-> 1 , 1 1-> 0
elif option == 'check': # * check x: S에 x가 있으면 1을, 없으면 0을 출력한다. (1 ≤ x ≤ 20)
check = (1 << int(arr[1])) # 10000 이렇게해서 값이 1이면 1, 0이면 9 출력
if bit & check: # '1'만 남아있으면 1이 맞으므로 print(1)
print(1)
else: # '0'만 남아있으면 0이므로 0
print(0)
# 반례
# 2
# all
# check 20
# 결과 : 1
3-2. 자바스크립트 코드 (javascript, js)
- 파이썬 코드를 그대로 자바스크립트로 옮겨서 풀어보았다.
- 비트마스킹 문법 자체는 파이썬과 자바스크립트가 거의 동일한 듯하다.
- readline을 이용하여 입출력을 처리했다.
- 참고로, 숫자.toString(2) 이렇게 만들면 숫자값을 2진수로 이루어진 문자열로 확인할 수 있다.
// * 비트마스킹 문제를 풀어보자
const readline = require("readline");
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
let M = null;
let mCount = 0;
let bit = 0;
const solution = (option, value) => {
if (!isNaN(value)) {
// 숫자이면
+value; // 숫자로 변경
}
switch (option) {
case "all":
// s를 1~..20 으로 바꾼다.
bit = 0b111111111111111111111;
break;
case "empty":
// S를 공집합으로 바꾼다.
bit = 0b0;
break;
case "add": //S에 X를 추가한다. 이미 있다면 무시
bit = bit | (1 << value); // OR연산으로 추가
break;
case "remove": // S에 X를 제거한다. 없는 경우는 연산을 무시한다.
/// 3번째를 뺀다면, 1000 => 0111 이렇게 바꿔서, and 연산을 해준다. and는 0->0 = 0이기 때문이다
bit = bit & ~(1 << value);
break;
case "check": // S에 X가 있으면 1을, 없으면 0을 출력한다. 1이랑 and 하면 된다.
if (bit & (1 << value)) {
console.log(1);
} else {
console.log(0);
}
break;
case "toggle": // S에 x가 있으면 x를 제거하고, 없으면 x를 추가한다. 1 xor 1->1 = 0 0->1 = 1
bit = bit ^ (1 << value);
break;
default:
break;
}
console.log(bit.toString(2)); // 2진수로 출력
return;
};
rl.on("line", (line) => {
if (!M) {
M = +line;
} else {
[option, value] = line.split(" ");
console.log(option, value);
solution(option, value);
mCount++;
}
if (mCount == M) {
rl.close();
}
}).on("close", () => {
process.exit();
});
4. 마무리
비트 연산에 대해 공부가 필요했었는데 이제는 조금 익숙해진 것 같다.이제 비트 연산을 응용해서 다른 문제도 풀어보아야겠다.
** 참고 풀이
- 아래 블로그 링크의 풀이가 정말 설명이 잘 되어 있어요!! https://coarmok.tistory.com/entry/%ED%8C%8C%EC%9D%B4%EC%8D%ACpython-%EB%B0%B1%EC%A4%80-11723%EB%B2%88-%EB%B9%84%ED%8A%B8%EB%A7%88%EC%8A%A4%ED%82%B9
읽어주셔서 감사합니다~
도움이 되셨다면 공감 부탁드립니다 😊
피드백 환영입니다 👍
'코딩테스트 > JavaScript' 카테고리의 다른 글
| [백준/21736/JavaScript] 헌내기는 친구가 필요해 풀이 (dfs, bfs, 자바스크립트, js) (2) | 2025.06.05 |
|---|---|
| [프로그래머스/javascript] 주식 간격 풀이 (문제 해설 포함, 자바스크립트, js) (1) | 2025.06.01 |
댓글