BOJ - 1946 신입사원

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

문제 유형 : 그리디 알고리즘

문제 티어 : 실버1 

문제 풀이 : 적어도 하나는 다른 지원자보다 떨어지면 안된다는 조건이 있기 때문에 1차 서류 심사와 2차 면접 시험 중 하나를 오름차순으로 정렬 후 나머지 하나를 비교해줘야 한다. 

 

 

 예를 들어 1차 서류 심사 점수를 오름차순으로 정렬한다고 치자. 그러면 가장 첫 번째 즉, 맨 위에 있는 사람은 1차 서류 점수는 1등일 것이다. 이 때 최대 인원을 뽑으려면 그 아래부터는 무조건 앞 사람보다는 순위가 더 높아야 한다. 1차 서류가 1등인 사람은 무조건 뽑힐 것이고 그 아래부터 윗 사람보다 2차 면접 순위가 높으면 뽑힐 수 있기 때문에 최대한 이 구조를 만들어줘야 한다는 것이다.  

 

 

 1) 먼저 T를 받아서 T번의 실행을 해주어야 한다.

 2)  1차 서류 심사 등수 기준으로 오름차순 정렬 해준다.

 3) 그 후 두 번째 부터는 내 이전 사람보다 2차 면접 심사 등수가 높아야 한다. 

 

const fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().split("\n");
let T = Number(input[0]);
let line = 1 // 현재 줄
// T만큼 수행
for(let t=0;t<T;t++){
    let N = Number(input[line]); // 해당 줄에서 받아줘야 함
    let arr = []; // 한 번의 케이스가 끝나고 빈 배열로 초기화 해줘야 함
    for(let i=line+1;i<=line+N;i++){ // line+1 줄부터 N개를 출력해줘야 함
        let data = input[i].split(" ").map(Number);
        arr.push(data);
       }
     // 1차 서류 기준으로 정렬 즉, 첫 번째 항목으로 오름차순 정렬
     arr.sort((a,b)=> a[0]-b[0]);
     let count = 0;
     let minValue = 100001;
     // arr 내에서 비교 해줌
     for(let [a,b] of arr){
        if(b < minValue) {
            minValue = b;
            count+=1;
          }
      }
      console.log(count);
      line=N+1; // 줄 바꿈
 }

 

시간복잡도 : 정렬을 사용했기 때문에 O(nlogn)이 나온다.