백준 1946 - 신입 사원

문제

1946번: 신입 사원

---

---

조건

• 각각의 사람은 서류심사 등수와 면접시험 등수를 가지고 있음.
• 두 가지의 등수가 누군가보다 모두 낮으면 탈락한다.
• 이 때, 선발할 수 있는 신입사원의 최대 인원수를 구해라
• 1≤T≤20, 1≤N≤100,000

---

입출력

접근법

사람	서류 등수	면접 등수	결과
A	3	6	D보다 모든 등수가 낮음
B	7	3	C보다 모든 등수가 낮음
C	4	2	합격
D	1	4	합격
F	5	7	C 혹은 D보다 모든 등수가 낮음
G	2	5	D보다 모든 등수가 낮음
H	6	1	합격

---

풀이 1 - 브루트포스

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());

        for (int i = 0; i < T; i++) {
            int N = Integer.parseInt(br.readLine());

	 
			//d_rank : 서류 등수  → d_rank[0] 의 값 : 첫번째 사람의 서류 등수
			//i_rank : 면접 등수  → i_rank[2] 의 값 : 세번째 사람의 면접 등수
            int[] d_rank = new int[N];
            int[] i_rank = new int[N];

            for (int j = 0; j < N; j++) {
                st = new StringTokenizer(br.readLine());
                d_rank[j] = Integer.parseInt(st.nextToken());
                i_rank[j] = Integer.parseInt(st.nextToken());
            }

			//fall : 탈락자 수
            int fall = 0;
            for (int j = 0; j < N; j++) {      // j : 기준이 되는 사람의 번호
                for (int k = 0; k < N; k++) {  // k : j와 비교할 사람의 번호
                    if (j == k) {
                        continue;
                    }
					// 크기가 크다는 것은 등수가 낮다는 것
                    if (d_rank[j] > d_rank[k] && i_rank[j] > i_rank[k]) {
                        fall++;
                        break;
                    }
                }
            }
            System.out.println(N - fall);
        }

    }
}

---

풀이 2 - 정렬을 통해 반복 횟수 줄이기

• 서류 등수를 정렬해서, 서류 등수는 볼 필요가 없어졌다.
• 특정 사람의 면접 등수는 무조건 위에 있는 사람들보다 높아야 합격!
• 또한, 위에 있는 사람들 중 면접 등수가 제일 높은 사람만 비교해도 된다!

사람	서류 등수	면접 등수	결과
D	1	4	합격
G	2	5	탈락
A	3	6	탈락
C	4	2	합격
F	5	7	탈락
H	6	1	합격
B	7	3	탈락

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());

        for (int i = 0; i < T; i++) {
            int N = Integer.parseInt(br.readLine());

			//객체를 담아야하므로 List를 선언
            List<rank> list = new ArrayList<>();

            for (int j = 0; j < N; j++) {
                st = new StringTokenizer(br.readLine());
                int document_rank = Integer.parseInt(st.nextToken());
                int interview_rank = Integer.parseInt(st.nextToken());
                list.add(new rank(document_rank, interview_rank));
            }

			//내가 임의로 만든 rank 객체를 정렬해야함.
            Collections.sort(list, new Comparator<rank>() {
                @Override
                public int compare(rank o1, rank o2) {
                    return o1.document - o2.document;
                }
            });

			//첫번째 사람의 면접 등수
            int highRank = list.get(0).interview;
            int fall = 0;

            for (int j = 1; j < N; j++) {
                if (list.get(j).interview > highRank) {
                    fall++;
                    continue;
                }

				// 면접 등수가 기존의 highRank 보다 높은 경우
                highRank = list.get(j).interview;
            }

            System.out.println(N - fall);
        }

    }

	//서류 등수와 면접 등수를 저장할 클래스 정의
    public static class rank {
        int document;
        int interview;

        public rank(int document, int interview) {
            this.document = document;
            this.interview = interview;
        }
    }
}