백준 1946 신입사원 java

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

문제를 풀이하면서 문제를 제대로 읽지 않아 한참을 방황했던 문제이다. 너무 당연스럽게 점수라고 생각을 하고 주어진 예제 입력을 가지고 예제출력 4와 3을 도출하려고 하니, 도무지 감이 잡히지 않았다. 문제를 다시 정독하니 서류 성적과 면접 성적의 순위를 기준으로 입력이 주어진다는 것을 깨칠 수 있었다.

문제 풀이 과정

1. 서류순위 기준으로 오름차순 정렬한다.

2. 면접순위를 순회하면서 이전 면접순위보다 높다면 (즉 순위의 값이 작다면 1등이 1순위이기 때문)

3. count를 1증가시키고, 면접 순위를 갱신해준다. (아래와 비교해주기 위해서)

 

소스코드

package baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
//https://www.acmicpc.net/problem/1946
public class Baek1946{
    static int tc;
    static int n;
    static List<Applicant> applicants = new ArrayList<>();
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        tc = Integer.parseInt(br.readLine());
        for(int t =0; t< tc; t++){
            applicants.clear();
            n = Integer.parseInt(br.readLine());
            for(int i=0; i<n; i++){
                String[] scores = br.readLine().split(" ");
                applicants.add(new Applicant(Integer.parseInt(scores[0]), Integer.parseInt(scores[1])));
            }
            Collections.sort(applicants);
            int passCount = 1; //첫번 째 합격자는 무조건 합격
            int compareRank = applicants.get(0).rRank;
            for (int i = 1; i < n; i++) {
                int targetRank = applicants.get(i).rRank;
                if (targetRank < compareRank) { // 이전지원자 보다 면접 순위는 더 높은 순위라면
                    compareRank = targetRank;
                    passCount++;
                }
            }
            sb.append(passCount).append("\n");
        }
        System.out.println(sb.toString());
    }
    static class Applicant implements Comparable<Applicant>{
        private int lRank;// 서류성적 순
        private int rRank; // 인터뷰 성적 순

        Applicant(int l, int r) {
            this.lRank = l;
            this.rRank = r;
        }
        @Override
        public int compareTo(Applicant o) {
            return this.lRank - o.lRank;
        }
    }
}

 

느낀점 : 그리디 문제로 훌륭하다고 생각한다. 그리 어렵진 않지만, 문제를 잘 읽고 파악하는 것이 중요하다를 알려준 문제랄까?