[백준 / Java] 1946번: 신입 사원 (그리디)

 

코테99 19일차 문제는 백준 1946번 '신입사원'이다.

 

---

 

문제 이해

•  테스트 케이스의 개수가 주어진다.
• 한 케이스에는 지원자의 숫자가 주어지고, 각 지원자의 서류심사 성적과 면접 성적의 순위가 공백을 사이에 두고 주어진다.
• 이때, 서류 심사 성적과 면접시험 중 적어도 하나가 다른 지원자보다 떨어지지 않으면 선발된다.
• 선발할 수 있는 최대 인원수를 출력한다.
• 단, 두 성적 순위는 동석차 없이 결정된다.

 

---

접근 방법

 

1. 서류 심사 성적 등수를 기준으로 정렬한다.
2. 면접 성적 등수를 비교하며 현재 순위가 가장 높은 순위보다 높다면(작으면),
3. 합격자를 추가하고  높은 순위를 갱신한다.

 

---

 

알고리즘 진행 순서

 

1. 테스트케이스를 입력받는다.
2. 입력받은 지원자 정보를 (서류 순위, 면접 순위) 형태로 저장한다.
3. 서류 순위를 기준으로 오름차순 정렬한다.
   • 즉, 서류 1등부터 N등까지 순서대로 탐색 가능
4. 면접 순위 비교를 통해 선발할 수 있는 인원을 체크한다.
   • topRank(현재까지 선발된 사람 중 가장 높은 순위)를 갱신하면서 진행
   • 현재 지원자의 면접 순위 < topRank 이면 선발 가능
   • 선발할 때마다 topRank 를 갱신하면서 진행

 

---

구현 코드

package Boj;

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

public class Boj1946 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        int T = Integer.parseInt(br.readLine());

        for (int t = 0; t < T; t++) {
            int N = Integer.parseInt(br.readLine());
            int[][] applicants = new int[N][2];
            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine());
                applicants[i][0] = Integer.parseInt(st.nextToken());
                applicants[i][1] = Integer.parseInt(st.nextToken());
            }

            Arrays.sort(applicants, Comparator.comparingInt(a -> a[0]));

            int maxCount = 0;
            int topRank = Integer.MAX_VALUE;

            for (int[] applicant : applicants) {
                int interviewRank = applicant[1];

                if (interviewRank < topRank) {
                    maxCount++;
                    topRank = interviewRank;
                }
            }
            sb.append(maxCount).append("\n");
        }

        System.out.println(sb);
    }
}

 

---

회고

• 그리디 문제를 풀 때 어떤 것을 기준으로 정렬 후 다음 기준을 판단하는 지 감을 잡은 것 같다.
• 조금 더 어려운 문제들로 연습해보자!