백준 [java 자바] 1946번 : 신입사원

 

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

1946번: 신입 사원

겉으로 보기에는 쉬운 문제이지만 시간 초과가 너무 잘나서 빡빡한 문제입니다. 

 

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



class Main {
	
	
	
	public static void main(String[] arg) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader (System.in));
		StringTokenizer st;
        
		StringBuilder sb = new StringBuilder();
		
		
		
		int n = Integer.parseInt(br.readLine());
		
		int i;
		int j;
		
		for(i = 0;i<n;i++) {
			int cnt = 0;
			int a;
			
			int na = Integer.parseInt(br.readLine());
			int[] arr = new int[na+1];
			
			for(j = 1;j<=na;j++) {
				st = new StringTokenizer(br.readLine());
				a = Integer.parseInt(st.nextToken());
				arr[a] = Integer.parseInt(st.nextToken());
				
			}
			
			
			int k;
			
			int min = arr[1];
			
			for(j = 2;j<=na;j++) {
				if(arr[j]>min) {
					cnt++;
				}
				min = Math.min(arr[j], min);
			}
			sb.append(na-cnt + "\n");
			
		}System.out.println(sb);
		}
	
	 
}

어떤 한 사람이 다른 지원자에 비해(단 한사람이더라도) 두 개 다 순위가 낮은 것이 있으면 탈락이다.

처음에는 그냥 이차원 배열에 다 넣고 이차원 배열을 정렬하는 방법으로 했는데 시간 초과가 나왔다. 그래서 보완한 방법은 배열 하나를 만들고 입력을 받을 때마다 앞에 있는 수의 번호에 맞춰 들어가게 하는 방법을 쓰는 방법이다. 이래도 시간 초과가 나왔다. 원인은 내가 두 번째 것의 순위를 비교할 때 앞에 것을 하나하나 비교한 것이다. 배열 안에서 더 앞에 있는 요소의 수 중에 가장 높은 순위의 것만 보면 된다.(현재 배열보다 더 높은 것이 하나라도 있으면 탈락이므로) 이들을 차례로 센 다음에 시간 절약을 위해 sb.append를 사용했다.

 

 

 

 

알아야 할 점

1. 무언가 하나하나 비교할 것이 있으면 그중 제일 ~한 것만 비교하면 될 수도 있다.

2. 겹치는 것이 없는 배열은 그냥 차근차근 넣는 방법이 깔끔하다. 

 

다른 사람 코드와 다른 점 : 없다.