백준 1946 - 신입 사원

Java

1946 번 - 신입 사원

문제

진영 주식회사는, 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙을 세웠다. 즉, 어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류 심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않는다.

이러한 조건을 만족시키면서, 진영 주식회사가 이번 신규 사원 채용에서 선발할 수 있는 신입사원의 최대 인원수를 구하는 프로그램을 작성하시오.

접근 방법

Greedy로 해결하는 문제이다.
서류 성적과 면접 성적, 2개의 성적이 다른 사람과 비교하여 둘 다 떨어지는 사람의 수를 줄여가는 방식으로 접근하였다.
따라서 서류 심사 성적을 내림차순으로 정렬하였다. (아래에 있을 수록 서류 심사 성적이 높다)

# tc1
5 5
4 1
3 2
2 3
1 4
# tc2
7 3
6 1
5 7
4 2
3 6
2 5
1 4

이제 서류 심사 성적은 고려하지 않고, 면접 시험 성적이 정렬 된 아래 사람보다 더 낮으면(숫자가 크면) n명에서 하나씩 제거하는 방식으로 풀었다.

구현

처음에는 단순하게 2중 배열로 구현하였다.
위에서 부터 한명 씩 선택하여, 자신의 아래에 있는 사람들 중 면접 성적이 더 높은 사람이 있으면 사람 수를 1 차감하여 총 뽑히는 사람 수를 구했다.
1 ≤ N ≤ 100,000이므로, 최악의 경우 100,000 * 100,000이 되며 당연히 시간초과가 난다.

따라서 O(n)으로 구현하기 위해 int top을 사용하였다.
만약 자신의 면접 점수 순위가 3이라고 생각하자.
그렇다면 자신의 아래에 1, 2 면접 순위가 없으면, 아래의 사람들은 자신보다 서류 성적은 높아도 면접 성적은 자신보다 낮은게 되므로 뽑히게 된다.

따라서 top이라는 변수를 두어 현재 top보다 자신의 면접 점수가 높으면 아래에 자신보다 면접 성적이 높은 사람이 있다고 판단하여 총 사람 수에서 1 줄인다.

이제 top 변수를 세팅 해주어야 하는데, 이는 1에서부터 n까지 차례로 증가한다.
만약 1등을 만나면 top을 2로 세팅해주어, 이후 2등의 사람이 나오면 top이 2이고 이 뜻은 현재 2등 보다 높은 사람이 없다는 것이므로 뽑히게 된다(n에서 1 차감하지 않는다)

코드

import java.util.*;
import java.io.*;

public class Main {
	static int n, tcN;
	public static void main(String[] args) throws IOException {
		System.setIn(new FileInputStream("res/mainInput.txt"));	//제출 할 때 주석해야함
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk;
    	tcN = stoi(br.readLine());
    	for(int tc = 0; tc < tcN; tc++) {
    		n = stoi(br.readLine());
    		int result = n;
    		Pair[] p = new Pair[n];
    		for(int i = 0; i < n; i++) {
    			stk = new StringTokenizer(br.readLine());
    			p[i] = new Pair(stoi(stk.nextToken()), stoi(stk.nextToken()));
    		}
    		
    		Arrays.sort(p);
    		int v, idx;
    		boolean[] pivot = new boolean[n + 1];
    		int top = 1;
    		for(int i = 0; i < n - 1; i++) {
    			v = p[i].value;
    			if(v > top) {
    				result--;
    				pivot[v] = true;
    			}
    			if(v == top) {
    				pivot[v] = true;
    				idx = v;
					// 앞에서 부터 등수가 다 출현 했으면, top을 제일 뒤로 움직인다.
    				while(pivot[idx++] == true)
    					top++;
    				top++;
    			}
    		}
    		System.out.println(result);
    	}
    	
    	br.close();
	}
	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
	public static class Pair implements Comparable<Pair>{
    	int key;
    	int value;
    	Pair(int k,int v){
    		key = k;
    		value = v;
    	}
		public int compareTo(Pair o) {
			return -Integer.compare(key, o.key);
		}
	}
}

총평

난이도

⭐⭐⭐★★

후기

나만의 방식으로 해결한 그리디

개선할 점

없