[node.js] 버블 소트 ( 백준 1377번 )

첫번째부터 두번째까지는 버블 정렬을 시도한 것이다. 그런데 시간 초과가 나왔다.

아니, 문제가 버블 정렬인데 버블 정렬 했다고 시간 초과라니, 문제가 잘못된 것 아닌가 해서 봤더니,

A에 들어있는 수가 100만까지 나올 수 있다고 한다.

버블 정렬은 O(n^2) 이었으니까 100만의 제곱이면... 아하, 이건 해결할 수 없는 방식이었다.

이 문제는 버블 정렬을 시키진 않을 거면서 버블 정렬을 하면 몇 번이나 걸리는지를 묻는 문제였다.

그래서 방식을 바꾼 게, 버블 정렬이 어떤 조건에서 발생하는지를 보는 것이었다.

버블 정렬을 하면 각 자리 수는 좌측으로 한 칸씩 이동하게 된다.

예를 들어 예제처럼,

10, 1, 5, 2, 3의 숫자가 있다고 해보자.

1, 2, 3, 5, 10으로 정렬되어야 한다.

그러면 1은 좌측으로 1번, 2는 좌측으로 2번, 3은 좌측으로 2번 이동하게 된다.

5나 10은 자신의 인덱스보다 우측으로 가야 하는데, 우측으로 가는 건 버블 정렬 시 한 번에 가게 되므로 무시한다.

( 버블 정렬은 맨 끝자리부터 정렬하는 방식이기 때문이다. )

그러므로 답은 2가 되고, 이 문제에서는 1부터 숫자를 파악하기 때문에 + 1 해줘서 답이 3이 되는 것이다.

이를 이용해서 작업했더니 또 틀렸다.

이유는 같은 숫자 (...) 가 여러 번 들어올 수 있다는 조건 때문이었다. 이건 미처 생각을 못했다.

그래서 Set을 이용해서 풀어보려고 했는데 런타임 에러가 나왔다.

그냥 자료구조를 직접 만드는 게 낫다는 생각을 했고, 그 결과 정답이 되었다.

Set 자료구조를 내가 잘 다룰 줄 모르는 모양이다.

const readline = require("readline");

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

const input = [];
let count = 0;
rl.on("line", (line) => {
    if (!count) {
        count = Number(line);
    } else {
        input.push(Number(line));
        if (input.length === count) {
            rl.close();
        }
    }
}).on("close", () => {
    const numbers = input
        .map((el, i) => {
            return {
                value: el,
                index: i,
            };
        })
        .sort((a, b) => a.value - b.value);

    let maxValue = 0;
    for (let i = 0; i < count; i++) {
        maxValue = Math.max(maxValue, numbers[i].index - i);
    }

    console.log(maxValue + 1);
});

다른 사람의 코드에서 내가 기존에 하던 방식과 다르게 close에 코드를 짜는 것을 보았다.
그래서 나도 이렇게 해보았는데, 글쎄, 더 좋은 방법이 있을 것 같기도 하다.