백준 11723번: 집합 - javascript

3 분 소요

백준 11723번: 집합

문제 설명

접기/펼치기

비어있는 공집합 S가 주어졌을 때, 아래 연산을 수행하는 프로그램을 작성하시오.

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를 공집합으로 바꾼다.

입력

첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다.

둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다.

출력

접기/펼치기

check 연산이 주어질때마다, 결과를 출력한다.

예시

접기/펼치기

입력
26
add 1
add 2
check 1
check 2
check 3
remove 2
check 1
check 2
toggle 3
check 1
check 2
check 3
check 4
all
check 10
check 20
toggle 10
remove 20
check 10
check 20
empty
check 1
toggle 1
check 1
toggle 1
check 1

접근

문제를 제한조건을 보면 메모리제한이 4MB로 매우 작은 것을 알 수 있다.
~~물론 아래에 추가로 자바는 448mb c#은 64mb 등 메모리 제한이 추가되어있다~~
이 문제는 포스팅하는 현재로서는 node.js 를 사용해서 풀 수 없다!..
(그래서 문의를 넣어놨는데, 나중에는 가능 할 지도?)

먼저 이번 문제는 2가지 풀이가 가능하다.
만약 위의 문제를 풀기위해 빈 배열을 두고 매번 명령어에 따라 숫자를 넣거나 제거하고 숫자가 있는지 체크한다고 해보자.
그러면 매번 배열을 탐색하고 삽입,삭제를 해야 될 것이다.
그러면 주어진 메모리안에 코드가 돌아가지 못 할 것이고 우리는 배열에 일일히 넣지않아도 주어지는 명령어에 따른 숫자를 처리해야한다.

힌트는 바로 X의 범위에 있다.
X는 1이상 20이하의 수로 주어진다고 했는데 그러면 관리해야하는 인덱스도 1 ~ 20이다.
그리고 각 인덱스가 기억해야되는건 단 2가지다.
숫자가 존재하는지, 존재하지 않는지.
바로 2진수랑 같다.
2진수의 각 자리수는 2의n제곱값이다. 그러니 원하는 숫자가 들어올때마다 2의 지수로 계산해서 s에 2의 n제곱값을 넣어주면된다.
그리고 비트마스크를 이용해서 or 연산이나 and 연산을 사용하면 해당 비트가 존재하는지, 혹은 해당 비트를 무조건 1으로 변경해 줄 수 있다!
비트연산은 여기를 참고하자.

혹은,

여태 재귀문제를 풀면서 썼던 방법인데, 그냥 boolean 배열을 만들어 써도 된다.
boolean 배열도 각 인덱스값은 true나 false로 나뉘기 때문에 오히려 더 쉽다.

아래의 코드 중 JS코드는 위에서 맨처음에 설명한대로 일단 메모리 초과가 나는 상태이다.
정답이 필요하면 c++로 똑같이 바꿔서 사용하면 된다.

c++코드

접기/펼치기

#include

using namespace std;

int main() { ios::sync_with_stdio(NULL); cin.tie(nullptr); int M,x; int k = 0; string s; cin » M; while (M–) { cin » s; if (s == “add”) { cin » x; if(~(k & (1 «x))) k |= (1 « x); } else if (s == “remove”) { cin » x; if (k & (1 « x)) k &= ~(1 « x); } else if (s == “check”) { cin » x; if (k & (1 « x)) cout « 1 « “\n”; else cout « 0 « “\n”; } else if (s == “toggle”) { cin » x; if (k & (1 « x)) k &= ~(1 « x); else k |= (1 « x); } else if (s == “all”)k |= (1 « 21) - 1; else k = 0; } }

정답 코드

const readline = require('readline');
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});
let input = [];
let s = 0;
let result = [];
rl.on('line', function (line) {
  input.push(line);
})
  .on('close', async function () {
  // 답안 작성
  const n = input.shift()*1;
  input.reduce((acc,cur)=>{
    let line = cur.split(' ');
    bit_set(line[0],Math.pow(2,line[1]*1-1));
  },'');
  console.log(result.join('\n'));  
  process.exit();
});

let bit_set = function(cmd,n){
  switch(cmd){
    case 'add':
      s = s|n;
      break;
    case 'remove':
      if((n&s)===n)s-=n;
      break;
    case 'check':
      if((n&s)===n)result.push(1);
      else result.push(0);
      break;
    case 'toggle':
      if((n&s)===n)s-=n;
      else s+=n
      break;
    case 'all':
      s=0b11111111111111111111;
      break;
    case 'empty':
      s=0;
      break;
  }
}

정답코드2 boolean 배열사용

const readline = require('readline');
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});
let input = [];
let s = new Array(21).fill(false);
let result = [];
rl.on('line', function (line) {
  input.push(line);
})
  .on('close', async function () {
  // 답안 작성
  const n = input.shift()*1;
  input.reduce((acc,cur)=>{
    let line = cur.split(' ');
    bit_set(line[0],line[1]*1);
  },'');
  console.log(result.join('\n'));
  process.exit();
});

let bit_set = function(cmd,n){
  switch(cmd){
    case 'add':
      s[n] = true;
      break;
    case 'remove':
      s[n] = false;
      break;
    case 'check':
      if(s[n])result.push(1);
      else result.push(0);
      break;
    case 'toggle':
      if(s[n])s[n]=false;
      else s[n]=true;
      break;
    case 'all':
      s = new Array(21).fill(true);
      break;
    case 'empty':
      s = new Array(21).fill(false);
      break;
  }
}

Twitter Facebook LinkedIn

ryeon

백준 11723번: 집합 - javascript