백준 1946: 신입 사원

풀이 1

• 좋은 비교 방법이 떠오르지 않아 N개의 요소를 나머지 N개와 비교했다
• flag변수를 사용해 비교 중 탈락한 경우 비교를 중단해 시간을 조금이라도 줄이고자 했지만 시간복잡도는 O(N^2)로 좋지않은 풀이다.

결과 : 시간 초과

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Problem1946 {
    static int caseNum, appNum, answer;
    static ArrayList<int[]> scrLst;
    

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String sCase = br.readLine();
        caseNum = Integer.parseInt(sCase);

        for(int n = 0; n < caseNum; n++){
            scrLst = new ArrayList<>();
            answer =  0;
            String sApp = br.readLine();
            appNum = Integer.parseInt(sApp);

            for(int i = 0; i < appNum; i++){
                String sScr = br.readLine();
                StringTokenizer st = new StringTokenizer(sScr, " ");

                int[] temp = new int[]{Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())};
                scrLst.add(temp);
            }

            for(int i = 0; i < scrLst.size(); i++){
                int[] curScr = scrLst.get(i);
                int rFlag = 0;
                for(int j = 0; j < scrLst.size(); j++){
                    int[] compScr = scrLst.get(j);
                    if(curScr[0]>compScr[0] && curScr[1]>compScr[1]){
                        rFlag = 1;
                        break;
                    }
                }
                if(rFlag==0){
                    answer++;
                }

            }

            System.out.println(answer);

        }
    }
}

풀이2

풀이 참조
https://sihyungyou.github.io/baekjoon-1946/

• 첫번째 등수(서류)를 기준으로 정렬한 후 첫번째 등수가 가장 높은 사람을 기준으로 삼는다.
• 기준의 두번째 등수(면접)보다 등수가 낮으면 첫번째, 두번째 등수가 기준보다 낮으므로 탈락, 비교자의 두번째 등수가 기준보다 높으면 비교자의 등수로 기준등수를 업데이트.
• 시간복잡도 O(N)으로 기준과 한번 씩만 비교하면 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Problem1946_2 {
    static int caseNum, appNum, secRnk, answer;
    static ArrayList<int[]> rnkLst;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String sCase = br.readLine();
        caseNum = Integer.parseInt(sCase);

        for(int n = 0; n < caseNum; n++){
            rnkLst = new ArrayList<>();
            answer =  1;
            String sApp = br.readLine();
            appNum = Integer.parseInt(sApp);

            for(int i = 0; i < appNum; i++){
                String sScr = br.readLine();
                StringTokenizer st = new StringTokenizer(sScr, " ");

                int[] temp = new int[]{Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())};
                rnkLst.add(temp);
            }

            rnkLst.sort(new Comparator<int[]>() {
                @Override
                public int compare(int[] o1, int[] o2) {
                    if(o1[0] < o2[0]){
                        return -1;
                    } else if(o1[0] == o2[0]){
                        return 0;
                    } else {
                        return 1;
                    }

                }
            });

            secRnk = rnkLst.get(0)[1];
            for(int i = 1; i < rnkLst.size(); i++){
                if(rnkLst.get(i)[1] < secRnk){
                    answer++;
                    secRnk = rnkLst.get(i)[1];
                }


            }

            System.out.println(answer);

        }
    }
}