백준 20310번 - 타노스(Node.js/Javascript)

백준 20310번 - 타노스

문제

https://www.acmicpc.net/problem/20310

 

 

알고리즘 분류 : 그리디 알고리즘 문자열

 

 

---

문제 설명

문자열 S에서 0과 1의 절반을 제거하고 새로운 문자열 S'를 만들고, 이 때 가능한 문자열 중 사전순으로 가장 빠른 것을 구하는 것이다.

예를 들어, 101010101010이 입력으로 주어진다면, 1의 총 개수의 절반인 3개를 지울 수있고, 0의 총 개수의 절반인 3개를 지울 수 있다.

이때의 답은 000111이 된다.

그리고, 0과 1의 개수는 무조건 짝수이고, 중요한 것이 새로운 문자열을 만들때 재배치를 하면 안되고 순서는 유지해야된다.

예를 들어, 11110000이 입력으로 주어진다면, 재배치를 포함한다면 0011이 사전순으로 가장 빠른 것이다. 하지만, 재배치는 허용이 안되니 사전순으로 가장 빠른 것은 1100이 답이 된다.

 

이 문제를 풀기 위해서 구조적으로 재배치를 하지않고 사전순으로 가장 빠른 답을 찾기 위해서는 1은 앞에서부터 지우고, 0은 뒤에서부터 지우면 결과적으로 재배치를 하지않고 사전순으로 가장 빠른 답을 구할 수 있다.

 

 

---

나의 첫번째 풀이

    

      
      
      
      
    
const readline = require("readline");
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});
let input;
rl.on("line", function (line) {
    input = line;
    rl.close();
}).on("close", function () {
    input = input.split("");
    let count = parseInt(input.length / 2);
    let oddIndex = 0;
    let evenIndex = input.length - 1;
    for (let i = 0; i < count; i++) {
        if (i % 2 === 0) {
            // 홀수일때 odd
            // 앞에서부터 1제거
            input.splice(oddIndex, 1);
            oddIndex += 1;
            evenIndex -= 1;
        } else {
            // 짝수일때 even
            // 뒤에서부터 0제거
            input.splice(evenIndex, 1);
            evenIndex -= 2;
        }
    }
    console.log(input.join(""));
    process.exit();
});

이 풀이는 위에서 설명한 로직대로 짠것같다고 생각했지만, 11101011을 입력을 넣게되면 사전순으로 가장 빠른 답은 0111이 되어야 하지만, 출력으로는 1011이 나온다. 

서브태스크1에 너무 치중한 나머지, 앞에서 삭제해야하는 값과 뒤에서 삭제해야하는 값이 0인지 1인지 판별하는 조건을 빼먹었다.

 

 

---

두번째 풀이

    

      
      
      
      
    
const readline = require("readline");
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});
let input;
rl.on("line", function (line) {
    input = line;
    rl.close();
}).on("close", function () {
    input = input.split("").map(Number);
    let zeroArr = [];
    let oneArr = [];
    input.map((el, i) => (el === 0 ? zeroArr.push(i) : oneArr.push(i)));
    // zeroArr은 뒤에서 parseInt(zeroArr.length / 2)만큼 제외시킴
    let zeroCount = parseInt(zeroArr.length / 2);
    zeroArr = zeroArr.slice(0, zeroArr.length - zeroCount);
    // oneArr은 앞에서 parseIntI(oneArr.length / 2)만큼 제외시킴
    let oneCount = parseInt(oneArr.length / 2);
    oneArr = oneArr.slice(oneArr.length - oneCount, oneArr.length);
    let answer = "";
    let zeroPointer = 0;
    let onePointer = 0;
    while (zeroPointer < zeroArr.length && onePointer < oneArr.length) {
        if (zeroArr[zeroPointer] < oneArr[onePointer]) {
            answer += "0";
            zeroPointer++;
        } else {
            answer += "1";
            onePointer++;
        }
    }
    while (zeroPointer < zeroArr.length) {
        answer += "0";
        zeroPointer++;
    }
    while (onePointer < oneArr.length) {
        answer += "1";
        onePointer++;
    }
    console.log(answer);
    process.exit();
});

로직은 처음 생각했던대로 0은 뒤에서부터 삭제하고, 1은 앞에서부터 삭제하는 로직으로 작성하였다.

하지만, 이 코드에서 조금 다른 점은 입력에서 0인 인덱스 집합의 배열, 1인 인덱스 집합의 배열을 따로 설정하고, 이때의 각각의 배열에서 각각의 절반만큼 0은 뒤에서 삭제하고, 1은 앞에서 삭제하는 방식을 사용하였다.

이후에, while 문으로 각각의 배열에서 인덱스가 빠른것부터 문자열을 추가하는 방식으로 사용하여 풀었다.