백준 1946번 Node.js 풀이

문제 링크

- 내 풀이 (시간 초과)

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

const T = Number(input.shift());

const answer = [];

for (let i = 0; i < T; i++) {
  const N = Number(input.shift());

  const gradeArr = [];

  for (let j = 0; j < N; j++) {
    const grade = input.shift().split(" ").map(Number);

    gradeArr.push(grade);
  }

  let count = 0;

  for (let k = 0; k < gradeArr.length; k++) {
    const [document, interview] = gradeArr[k];

    for (let z = 0; z < gradeArr.length; z++) {
      if (k === z) {
        continue;
      }

      const [doc, int] = gradeArr[z];

      if (doc < document && int < interview) {
        count++;
        break;
      }
    }
  }

  console.log(N - count);
}

역시나 2중 반복문을 돌면 시간초과일거 같은데.. 라고 생각하면서 일단 코드를 짜보았지만 역시나였다.

- 수정 풀이

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

const T = Number(input[0]);

let answer = [];

let line = 1;

for (let i = 0; i < T; i++) {
  const N = Number(input[line]);

  const gradeArr = [];

  for (let j = line + 1; j <= line + N; j++) {
    const grade = input[j].split(" ").map(Number); // 수정

    gradeArr.push(grade);
  }

  const sortedGradeArr = gradeArr.sort((a, b) => a[0] - b[0]);

  let count = 0;

  const firstGrade = sortedGradeArr[0];

  for (let [document, interview] of sortedGradeArr) {
    if (firstGrade[0] < document && firstGrade[1] < interview) {
      count++;
    } else {
      firstGrade[0] = document;
      firstGrade[1] = interview;
    }
  }

  answer.push(N - count);
  line += N + 1;
}

console.log(answer.join("\n"));

일단 2중 반복문을 sort 메서드로 정렬을 해준후 단일 반복문을 도는 방향으로 고쳐주었다.

그리고 input.shift()부분이 문제였는데, input.shift()를 해주는 경우 배열이 전체적으로 다시 조정이되므로 시간복잡도가 그만큼 늘어난다.

인풋라인이 많더라도 line이라는 변수를 통해서 input 그 자체에 접근할수 있도록 했다.