백준 1946번 신입사원 - node.js

해당 포스팅은 백준 1946번 신입사원 풀이를 다룬다. 문제 링크
코드는 javascript로 작성하였다.

문제

문제 설명

• 인재 선발 시험은 1차 서류심사와 2차 면접시험으로 이루어진다.
• 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다.
• 선발할 수 있는 신입사원의 최대 인원수를 구하는 프로그램을 작성하시오.

입력

• [첫째 줄] : 테스트 케이스의 개수 T(1 ≤ T ≤ 20)
• [테스트 케이스] :
  • [첫째 줄]: 지원자의 숫자 N(1 ≤ N ≤ 100,000)
  • [둘째 줄]:
    1. N개 줄에는 각각의 지원자의 서류심사 성적, 면접 성적의 순위가 공백을 사이에 두고 한 줄에 주어진다
    2. 두 성적 순위는 모두 1위부터 N위까지 동석차 없이 결정된다고 가정한다.

출력

각 테스트 케이스에 대해서 진영 주식회사가 선발할 수 있는 신입사원의 최대 인원수를 한 줄에 하나씩 출력한다.

풀이

적어도 하나가 다른 지원자보다 떨어지지 않는다는 곧 서류심사와 면접시험 두 개가 하나라도 다른 지원자보다 높은 사람을 뽑겠다는 의미이다. 따라서 면접자가 A라고 할 때, A는 "자신보다 서류심사 성적이 높은 면접자들의 면접심사 성적보다 면접 성적이 높아야" 선발될 수 있다.

그렇다면 이를 어떻게 구현해야 할까?

문제에서 성적 순위에는 동석차가 없다고 주어졌으므로, 서류심사를 기준으로 오름차순 정렬을 한 다음, 차례로 면접심사 성적 upper를 기록한다. 면접자의 면접심사 성적이 upper보다 높다면 선발된 것이므로, upper을 그의 면접심사 성적으로 업데이트 한 다음 cnt += 1을 해주면 된다.

예제 & 로직

예제의 첫 번째 테스트케이스를 통해 설명하겠다.

1. 서류성적을 기준으로 오름차순 정렬을 한다.
2. 선발될 지원자 수 cnt를 0으로 선언한다.
   면접심사 성적 upper을 Number.MAX_SAFE_Integer로 선언한다.
3. 지원자들에 대해 loop를 돌면서 면접성적 < upper일 시,
   1) upper을 지원자의 면접 성적으로 업데이트 한다음,
   2) cnt += 1을 해준다.

전체 코드

const input = require('fs').readFileSync('/dev/stdin').toString().split('\n').slice(0, -1);
const parsed = input.map(str => str.split(' ').map(c => parseInt(c)));

const t = parsed.shift();

// input을 각 테스트에 대한 배열로 변경
const tests = [];

for (let i = 0; i < parsed.length; i++) {
    const line = parsed[i];
    
    if (line.length === 1) {
        const [n] = line;
        tests.push(parsed.slice(i + 1, i + n + 1).sort(([a], [b]) => a - b));
        i += n;
    }
}

const ans = [];
// 각 테스트에 대한 결과 체크
for (let test of tests) {
    let cnt = 0;
    let upper = Number.MAX_SAFE_INTEGER;
    
    for (let i = 0; i < test.length; i++) {
        const [a, b] = test[i];
        
        if (b < upper) {
            cnt += 1;
            upper = b;
        }
    }
    
    ans.push(cnt);
}

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