[JavaScript] 백준 1946 신입 사원 (JS)

신입 사원

📚 문제 설명

신입 사원을 채용하는데 1차 서류 심사, 2차 면접 시험으로 뽑는다고 한다.
이 두개의 시험 중에서 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다고 할 때, 이 회사에서 신입사원의 최대 인원은 몇명인가.

즉, 모든 신입 사원은 각자 한가지 분야는 다른 사람보다 자기가 높아야 한다.

👨🏻‍💻 풀이 과정

일단 지원자들을 1차 서류 심사 기준으로 정렬을 진행한 후에 생각을 해보자.
그 후에 1등부터 차례로 뽑는다고 가정을 해보자.

그리고 1차 성적순으로 뽑은 후에 2차 면접 시험순으로 다시 한번 정렬을 진행한다고 하면,
다음으로 뽑을 사람은 무조건 이미 뽑힌 사람들보다 2차 성적이 높아야 한다.
( 1차는 정렬을 통해 다음 확인할 사람은 어차피 1차 성적이 더 낮다.)

예시를 이용해 설명하자면, 합격자들의 1차 성적과 2차 성적은 반드시 다음과 같아야 한다.

지원자 / 1차 성적 / 2차 성적
---
A / 1 / 4
B / 2 / 3
C / 3 / 2
D / 4 / 1

다음과 같이 1차 성적을 오름차순으로 정렬하면 2차 성적은 반대로 내림차순으로 정렬이 되어야 한다.

그렇게 만든 첫번째 풀이는 다음과 같다.

전체 풀이

    let fs = require("fs");
    let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
    let N = input.shift();
    let answer = [];
	// 각각의 테스트 실행 함수
    const PickPerson = (INPUT) => {
      	// 전체 지원자 수
        let TotalPerson = parseInt(INPUT.shift());
      	// 각각의 지원자의 점수 배열
        const PersonArr = INPUT.splice(0, TotalPerson).map(v => v.split(' ').map(Number));
      	// 1차 성적순으로 정렬
        PersonArr.sort((a, b) => a[0] - b[0]);
        let stack = [];
      	// 전체 지원자들 만큼 반복문
        for (const personArrElement of PersonArr) {
          // 만약 스택에 이미 존재하면 진행
            if (stack.length) {
              // 이미 스택의 마지막 값보다 순위가 높아야함
                if (stack[stack.length - 1] > personArrElement[1]) {
                    stack.push(personArrElement[1]);
                }
              // 만약 스택이 비어 있으면 우선 1차 1등부터 넣어준다.
            } else {
                stack.push(personArrElement[1]);
            }
        }
        answer.push(stack.length);
    };
	// 테스트 횟수만큼 실행
    const solution = () => {
        for (let i = 0; i < parseInt(N); i++) {
            PickPerson(input);
        }
    };
    solution();
    console.log(answer.join('\n'));

🧐 후기

이 문제를 보고 처음에는 PQ를 이용하면 되는 문제일 줄 알았는데 더 생각을 해보니 굳이 PQ를 구현하여 사용할 필요가 없는 문제였다.
만약, sort를 계속 해야하는 문제였다면, PQ를 이용하는게 좋았겠지만, 해당 문제에서는 그럴 필요가 없기 때문이다.