[백준 / 1946 신입 사원 / JAVA]

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

1946번: 신입 사원

 

문제 설명

처음엔 2중 for문으로 시간 초과가 나서 Map을 쓰는 방법도 써봤는데 이것도 초과에 걸렸다.

느낌상 합격자를  찾는 과정에서 2중 for문을 쓰면 시간초과가 걸리는 것 같다.

 

rating 배열 하나로 인덱스에는 서류 순위를, 인덱스 밸류에는 면접 순위를 저장한다.

이후 면접 순위를 비교하기 위한 compareItvScore에 서류 1등의 면접 순위를 저장

다음 반복문에서 2등부터 면접 순위를 compareItvScore와 비교한다.

 

순위가 높다면 면접 합격자 +1, compareItvScore도 해당 합격자의 면접 순위로 초기화시켜준다. → 배열이 서류 순위 순서대로 진행되서 서류 순위는 지고 시작하기에 면접 순위라도 높아야 하는데 합격하기 위해선 나보다 서류 순위가 높은 사람들의 면접 순위를 모두 이겨야해서 compareItvScore를 초기화 시키는 것

 

이후 최대 합격자 출력

 

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

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 t=0; t<T; t++) {
			int N = Integer.parseInt(br.readLine());
			int[] rating = new int[N+1];
			
			for(int n=1; n<=N; n++) {
				st = new StringTokenizer(br.readLine());
				int docsScore = Integer.parseInt(st.nextToken());
				int interviewScore = Integer.parseInt(st.nextToken());
				
				rating[docsScore] = interviewScore;
			}
			
			int maxPerson = 1;
			int compareItvScore = rating[1]; // 문서 점수 1등의 면접 점수로 비교
			
			for(int i=2; i<=N; i++) { // 1등은 이미 통과처리
				if(rating[i] < compareItvScore) { // 정렬됐기에 서류 순위는 지고 시작, 면접 순위라도 높아야한다.
					maxPerson++;
					compareItvScore = rating[i]; 
				}
			}
			System.out.println(maxPerson);
		}
	}
}