[백준/JS] 1946 신입사원

 

문제링크: https://www.acmicpc.net/problem/1946

1946번: 신입 사원

 

정렬 + 그리디 문제이다.

첫번째 점수를 기준으로 정렬을 하고, 순회하면서 두번째 점수가 더 작은 값일때 count 를 하면된다.

 

1. 서류심사 성적을 기준으로 정렬을 한다.

2. target 이라는 Number.MAX_SAFE_INTEGER 를 저장한 변수를 생성한다.

2-1. if (target > 두번째 점수) 를 만족할 경우 target 을 갱신하고 count 를 +1 한다.

 

const fs = require('fs');

BOJkey = false;

let input = fs
  .readFileSync(BOJkey ? './javascript/1946/input.txt' : './dev/stdin')
  .toString()
  .trim()
  .split('\n')
  .reverse();

const answer = [];
const T = Number(input.pop());

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

  const data = [];
  for (let j = 0; j < N; j++) data.push(input.pop().split(' ').map(Number));
  data.sort((a, b) => a[0] - b[0]);

  let [target, count] = [Number.MAX_SAFE_INTEGER, 0];
  for (let j = 0; j < N; j++) {
    if (target > data[j][1]) {
      target = data[j][1];
      count++;
    }
  }

  answer.push(count);
}

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

 

시간 복잡도: O(T * N)