[BAEKJOON] 1931번 : 신입사원 (JAVA)

- 알고리즘 분류 : 그리디

- 사용 언어 : JAVA

- 문제 요점

1. 점수를 입력받는 것이 아닌, 등수를 입력받는 것임 (중요)
2. 나를 제외한 모든 참가자와 비교를 해야함.
   1. 서류 등수와 면접 등수가 있음.
   2. 어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류 심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않는다.
   3. 서류 등수를 배열의 인덱스로 두고, 배열의 값을 면접 등수로 둔다.

 

이해가 잘 안됐던 문제이며, 이중 반복문을 쓰면 시간 제한으로 인해 쉽지 않았던 문제이다.

아래의 블로그를 보고 방향성을 잡았다.

 

참고한 블로그 : https://kosaf04pyh.tistory.com/113

[알고리즘 문제] 백준1946 - 신입사원

 

소스 설명은 주석을 참고해주세요.

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

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		// T : 테스트케이스의 갯수
		int T = Integer.parseInt(br.readLine());
		
		// result : 테스트케이스의 각 결과를 가지는 배열
		int[] result = new int[T];
		
		// 테스트케이스의 수만큼 반복
		for(int i=0; i<T; i++) {
			
			// N : 사람의 수
			int N = Integer.parseInt(br.readLine());

			// 사람이 한 명일 때
			if(N==1) {
				result[i]=1;
				continue;
			}
			
			// 합격할 수 있는 사람의 수
			int count = 0;
			
			int[] scoreMap = new int[N+1];
			for(int j=0; j<N; j++) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				
				// s1 : 서류 등수
				// s2 : 면접 등수
				int s1 = Integer.parseInt(st.nextToken());
				int s2 = Integer.parseInt(st.nextToken());
				
				scoreMap[s1] = s2;
			}
			
			// 서류 등수가 1등이라면 무조건 합격 
			// 1등의 면접 등수를 저장한다.
			int nowS2 = scoreMap[1]; 
			// count 증가
			count++;
			
			// 위에서 1등은 합격시켰으니, 2등부터 확인한다.
			for (int k = 2; k <= N; k++) {
				
				// 합격하기 위해서는 앞 사람의 면접 등수보다 높아야 한다.
                if (nowS2 >= scoreMap[k]) {
                	
                	// 앞 사람의 면접 등수보다 높다면
                	// count 증가
                	count++;
                	
                	// 앞 사람의 면접 등수를 최신화
                	nowS2 = scoreMap[k];
                    
                }
            }
			
			// 결과를 배열에 넣는다.
			result[i] = count;
		}
		
		// 결과 출력
		for(int i=0; i<T; i++) {
			System.out.println(result[i]);
		}
		
	}

}