[알고리즘] 백준 1946 신입 사원 (javascript)

문제

언제나 최고만을 지향하는 굴지의 대기업 진영 주식회사가 신규 사원 채용을 실시한다. 인재 선발 시험은 1차 서류심사와 2차 면접시험으로 이루어진다. 최고만을 지향한다는 기업의 이념에 따라 그들은 최고의 인재들만을 사원으로 선발하고 싶어 한다.

그래서 진영 주식회사는, 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙을 세웠다. 즉, 어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류 심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않는다.

이러한 조건을 만족시키면서, 진영 주식회사가 이번 신규 사원 채용에서 선발할 수 있는 신입사원의 최대 인원수를 구하는 프로그램을 작성하시오.

입력

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

출력

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

나의 풀이

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
let index = 0;
const totalCase = parseInt(input[0])
index++


for (let i = 0; i < totalCase; i++) { 
    let count = Number(input[index]);
    index++;

    let array = [];

    for (let j = 0; j < count; j++) {
        let [a, b] = input[index].split(' ').map(Number);
        index++;
        array.push({ a, b });
    }
    const sortedArray = array.sort((c, d) => c.a - d.a);

    let value = 1; 
    let minInterviewRank = sortedArray[0].b;
    for (let k = 1; k < sortedArray.length; k++) {
        const currentValue = sortedArray[k].b
        if (currentValue < minInterviewRank) {
            value++;
            minInterviewRank = sortedArray[k].b;
        }
    }

    console.log(value);
}

설명

일단 첫 번째 입력값이 총 몇 개의 케이스가 오는지 오는 값이다.
그리고나서 신입사원의 숫자, 그리고 각 신입사원의 등수가 나오는 형태이다.

이 문제는 그리디 유형에 속한다.

일단 전략은 서류심사 점수를 기준으로 1등부터 나머지를 정렬시킨다.
그렇게 하면 조건상 1등은 무조건 합격이다.
그렇다면 1등의 면접점수를 일단 최소값으로 가지면서, 다음 2등을 살펴보아야 한다.
왜냐하면 2등은 자신보다 앞선 순위인 1등보다 면접점수를 잘 받아야 하기 때문이다.
그렇게 1등의 면접점수와 2등의 면접점수를 비교한다.
만약 2등이 1등보다 순위가 낮다면(면접을 잘봤다면) 2등 또한 합격이고, 2등의 면접점수가 1등보다 좋으므로 비교 순위를 2등값으로 할당한다.

이렇게 반복하게 되면 점점 서류의 후 순위인 사람이므로, 면접 순위는 반드시 앞선 사람들 모두의 순위보다 반드시 높아야 한다.

코드를 살펴보면 일단 index를 선언하여 0을 할당해뒀다.
그리고 인풋의 첫 번째 값을 구한 뒤 바로 index를 1 더했다.
그 이유는 index가 더해져야 그 다음 입력값을 활용할 수 있기 때문이다.

문제에 보면 첫 for문에서 바로 인풋값의 인덱스번호로 count값을 바로가져오는데 이는 앞서 index를 1 더해서 count값에 위치했기 때문이다.
이제 count값도 계산했으니 또 한번 index++를 통해 실제 면접자의 점수를 가져온다.

가져온 점수를 숫자로 잘 뽑은 뒤, 각각 a,b라는 키값으로 객체를 만든 뒤 배열에 삽입했다.
이렇게 첫 번째 케이스의 배열이 모이고 나면, 해당 배열을 서류점수 등수로 정렬시킨다.

그 다음 정렬된 배열을 가지고 아까 설명한것과 같이 1등은 무조건 합격이므로 value에 1명을 할당해두고, 현재까진 최소등수이므로 최소값에 등수를 할당한다.

그리고 그 다음 사람부터 for문을 통해 검사를 시작하고 그 다음사람의 등수가 최소등수보다 더 낮은 숫자면 최소등수를 갱신하고 value에 1을 더해 합격자 수를 추가한다.

나는 처음 위 방식을 이해하는데만 30분을 넘게 걸린것 같다.
사실 문제 자체는 이해되지 않았지만 테스트케이스를 보고 얼추 이렇게 풀어야 한다는 감은 잡았다. (사실 그리디 문제를 연속해서 풀다보니 그냥 이렇게 습관적으로 풀어버린것같다.)

앞으로는 좀 더 이런 유연한 사고를 할 수 있도록 머리좀 많이 써야겠다.