[백준BOJ] 1946번 신입 사원.java

 

백준 저지에서 신입 사원을 자바를 통해 풀어 보았다. 

 

https://www.acmicpc.net/problem/1946

1946번: 신입 사원

 

1946번 신입 사원.java

GitHub - tomy9729/Algorithm: 🐗 내가 직접 작성한 내 코드 🐗

 

1946번 신입 사원

문제

언제나 최고만을 지향하는 굴지의 대기업 진영 주식회사가 신규 사원 채용을 실시한다. 인재 선발 시험은 1차 서류심사와 2차 면접시험으로 이루어진다. 최고만을 지향한다는 기업의 이념에 따라 그들은 최고의 인재들만을 사원으로 선발하고 싶어 한다.
그래서 진영 주식회사는, 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙을 세웠다. 즉, 어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류 심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않는다.
이러한 조건을 만족시키면서, 진영 주식회사가 이번 신규 사원 채용에서 선발할 수 있는 신입사원의 최대 인원수를 구하는 프로그램을 작성하시오.

설명

각 지원자들은 서류심사 성적과 면접시험 성적이 존재하며 성적순으로 순위가 매겨진다. 만약 어떤 지원자가 다른 지원자의 서류심사 성적과 면접시험 성적 모두 떨어진다면 그 지원자는 결코 선발되지 않는다. 우선 모든 지원자들을 서류심사 성적 내림차순으로 정렬했다. 서류심사 성적은 정렬된 상태이기 때문에 면접시험 성적만 비교하면 선발 인원을 구할 수 있다. 

 

처음에는 이중반복문을 통해 완전 탐색을 생각했으나 시간 초과에 걸렸다. 각 지원자들의 합불 여부를 판단하기 때문에 최소 1번의 반복문을 써야한다. 따라서 1번의 반복문으로 선발 인원을 구하는 아이디어를 떠올려야 했다.

 

서류심사 성적을 기준으로 내림차순이기 때문에 어떤 지원자보다 뒤에 있는 배열에 대해서 면접시험 성적이 더 높은 지원자가 있으면 결코 선발되지 않는다. 즉 면접시험에서 가장 높은 성적을 갖는 지원자의 순위만 알고 있으면 합불 여부를 판단할 수 있다. 이는 어떤 지원자 A와 어떤 지원자 B에 관계에 대해 구하는게 아닌 지원자 A의 합불 여부만 판단하기에 가능하다.

 

배열의 뒤에서부터 시작해서 배열을 거꾸로 탐색한다. 면접시험 성적이 가장 높은 지원자의 성적을 저장한다. 만약 현재 저장한 성적보다 높은 성적의 지원자가 있으면 저장한 성적을 갱신한다. 만약 현재 저장한 성적보다 낮은 성적의 지원자가 있으면 해당 지원자는 뽑힐 수 없다.

코드

//1946번 신입 사원.java
package week5;

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

public class 신입_사원_1946 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();
    
    static class person implements Comparable<person>{
    	int rank1;
    	int rank2;
    	person(int rank1, int rank2){
    		this.rank1 = rank1;
    		this.rank2 = rank2;
    	}
    	@Override
		public int compareTo(person o) {
			int value = this.rank1 - o.rank1;
			return value*-1;
		}
		@Override
		public String toString() {
			return "person [rank1=" + rank1 + ", rank2=" + rank2 + "]";
		}
    	
    }
    static int T;
    static int N;
    static person[] people;
    static int answer;
    public static void main(String[] args) throws NumberFormatException, IOException {
		T = Integer.parseInt(br.readLine());
		for(int t=1;t<=T;t++) {
			N = Integer.parseInt(br.readLine());
			people = new person[N];
			
			for(int i=0;i<N;i++) {
				st = new StringTokenizer(br.readLine()," ");
				people[i]=new person(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()));
			}
			
			Arrays.sort(people);
			
			answer=N;
			int minR = Integer.MAX_VALUE;
			for(int i=N-1;i>=0;i--) {
				if(people[i].rank2 < minR) minR=people[i].rank2;
				else answer--;
			}
			sb.append(answer+"\n");
		}
		System.out.println(sb.toString());
	}
}