20310 타노스 node.js

백준 20310 타노스

어느 날, 타노스는 0과 1로 이루어진 문자열 $S$를 보았다. 신기하게도, $S$가 포함하는 0의 개수와 $S$가 포함하는 1의 개수는 모두 짝수라고 한다.
갑자기 심술이 난 타노스는 $S$를 구성하는 문자 중 절반의 0과 절반의 1을 제거하여 새로운 문자열 $S'$를 만들고자 한다.
$S'$로 가능한 문자열 중 사전순으로 가장 빠른 것을 구하시오.

문제를 읽었을 때 솔직히 잘 이해를 못했다.
처음에는 0과 1의 수를 센 후, 앞에서부터 0 그다음에 1을 입력했다.

ex)111110011001 -> 001111

그런데, 이렇게 제출하니 25점만 만족했다.
알고보니 문자의 재배열이 불가능하다는 사실...!

그래서 100점을 맞을 수 있는 풀이법은
앞에서부터 1을 지우고, 뒤에서부터 0을 지우면 된다!

풀이

const fs = require('fs');
const file = process.platform === 'linux' ? 'dev/stdin' : '../stdin.txt';
const input = fs.readFileSync(file).toString().trim().split('\n');
let string = input[0];
const count = [0, 0];
for (let i = 0; i < string.length; i++) count[string[i]] += 1;

const newCount = count.map((e) => Math.floor(e / 2));

let totalCnt = newCount[0];
let deleteList = [];
for (let i = string.length - 1; i >= 0; i--) {
  const currentChar = string[i];
  if (currentChar == 0) {
    deleteList.push(i);
    totalCnt -= 1;
  }
  if (totalCnt == 0) break;
}

const ans = string.split('');
deleteList.forEach((index) => {
  ans[index] = -1;
});

deleteList = [];
totalCnt = newCount[1];
for (let i = 0; i < string.length; i++) {
  const currentChar = string[i];
  if (currentChar == 1) {
    deleteList.push(i);
    totalCnt -= 1;
  }
  if (totalCnt == 0) break;
}
deleteList.forEach((index) => {
  ans[index] = -1;
});

console.log(ans.filter((el) => el != -1).join(''));