[BOJ-Silver1] 1946번 신입 사원

💡풀이

• 서류 순위 기준으로 오름차순
• 맨 앞에 있는 사람은 무조건 채용
• 두번째 사람부터 면접 순위가 앞사람들보다 높은지 확인

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		for(int  t= 0; t<T; t++){
			int n = Integer.parseInt(br.readLine());
			int[][] scores = new int[n][2];
			// 순위 입력
			for(int i = 0; i<n; i++){
				StringTokenizer st = new StringTokenizer(br.readLine());
				scores[i][0] = Integer.parseInt(st.nextToken());
				scores[i][1] = Integer.parseInt(st.nextToken());
			}

			int result = 1;
			// 서류 성적 순위 기준으로 오름차순
			Arrays.sort(scores, (a, b) -> Integer.compare(a[0], b[0]));
			int prevMin = scores[0][1];
			// 앞에 면접 순위 중 가장 작은 순위랑 비교해서 작으면 result +1
			for(int i = 1; i<n; i++){
				if (prevMin > scores[i][1]) {
					result++;
					prevMin = scores[i][1];
				}
			}
			System.out.println(result);
		}
	}
}

🚨시간초과

• 면접 순위 확인하는 코드에서 이중 for문으로 시간초과
• 앞에 사람들을 하나씩 확인하는게 아니라 앞 사람들 중 높은 순위를 계속 갱신하고 그걸 기준으로 확인

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		for(int  t= 0; t<T; t++){
			int n = Integer.parseInt(br.readLine());
			int[][] scores = new int[n][2];
			for(int i = 0; i<n; i++){
				StringTokenizer st = new StringTokenizer(br.readLine());
				scores[i][0] = Integer.parseInt(st.nextToken());
				scores[i][1] = Integer.parseInt(st.nextToken());
			}

			int result = 1;
			Arrays.sort(scores, (a, b) -> Integer.compare(a[0], b[0]));
			for(int i = 1; i<n; i++){
				int cnt = 0;
				for(int j = i-1; j>=0; j--){
					if (scores[i][1] < scores[j][1]) cnt++;
				}
				if (cnt == i) result++;
			}
			System.out.println(result);
		}

	}
}