[BOJ 1946] 신입 사원 - JAVA

오늘은 그리디 알고리즘 문제인 신입 사원을 풀었습니다.

사실 풀면서 그리디보단 정렬문제에 가깝다고 생각하며,, 풀었습니다ㅋㅋㅋ

 

어떻게 풀진 알겠는데,,, 시간 초과 나지 않게 푸는 방법을 몰라서 세시간 만에 풀었슴다..

 

이제 문제 설명가겠슴다...!!

이 방법은 개인적인 방법이며 최적의 솔루션이 아닐 수 있습니다.

구현 내용

 

 

사실 문제가 이해가 안되서.... 문제를 이해하는 시간도 많이 걸렸슴다...

 

 

구현 방법

생각해야할 것은

나보다 서류와 면접 등수가 전부 높은 사람은 없어야지 내가 뽑힌다는 것입니다.

 

그렇다면, 서류등수를 토대로 정렬 시킨다면

나의 앞에 있는 지원자들 보다 면접 등수가 높다면 선발이 될 수 있습니다.

 

더 자세한 설명은 주석을 통해 하겠습니다.

↓↓↓↓↓↓↓↓↓↓↓    ↓↓↓↓↓↓↓↓↓↓    ↓↓↓↓↓↓↓↓↓↓    ↓↓↓↓↓↓↓↓↓↓

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

class Node implements Comparable<Node>{
    int a;  //서류등수
    int b;  //면접등수
    Node(int a, int b){
        this.a = a;
        this.b = b;
    }
    int getA(){
        return this.a;
    }
    int getB(){
        return  this.b;
    }

    @Override
    public int compareTo(Node o) {  //서류등수 정렬
        return this.getA() - o.getA();
    }
}
public class Main{
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 입력
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        // 출력
        int testCase = Integer.parseInt(br.readLine()); //테스트 케이스
        int result = 1; //정렬된 가장 앞의 수는 조건에 만족하기에 1부터 시작한다.
        StringTokenizer stok;
        while(testCase>0){  //테스트케이스 만큼 반복
            int n = Integer.parseInt(br.readLine());    //지원자의 숫자
            ArrayList<Node> node = new ArrayList<>();   //순위를 담을 리스트
            for(int i=0;i<n;i++) {  //지원자 수 만큼 리스트에 담는다.
                stok = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(stok.nextToken()); //서류등수
                int b = Integer.parseInt(stok.nextToken()); //면접등수
                node.add(new Node(a,b));
            }
            Collections.sort(node); //서류심사 1등부터 정렬
            int min = node.get(0).getB();   //서류 심사에서 1등을 한 지원자의
                                            //면접 등수를 저장
            for(int i=1;i<n;i++){
                int data = node.get(i).getB();  //서류심사에서 2등한 사람부터
                                                //차례대로 저장
               if( data < node.get(i-1).getB() && min > data){
                   //현재 지원자의 면접등수가 서류등수가 높은 지원자의 면접등수보다 높고
                   //면접등수가 min 데이터(가장 낮은 면접등수) 보다 낮다면
                   result++;    //신규 사원에서 선발하고
                   min = data;  //면접 등수 데이터를 업데이트 시킨다.
               }
            }

            bw.write(String.valueOf(result)+"\n");  //현재 테스트케이스 값 출력
            testCase--; //다음 테스트 케이스
            result = 1; //결과값 reset
        }

        bw.flush();
    }
}