백준#1946 - 신입 사원

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

1946번: 신입 사원

그리디 알고리즘으로 분류된 1946 신입사원 문제 입니다.

 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace _1946
{
    class Program
    {
        //Program 클래스 안에서만 사용할 지원자 클래스 정의.
        class Applicant : IComparable
        {
            //첫번째 시험의 등수, 두번째 시험의 등수를 멤버 변수로 가짐.
            public int first;
            public int second;
 
            public Applicant(int first, int second)
            {
                this.first = first;
                this.second = second;
            }
 
            //첫번째 시험을 기준으로 정렬.
            public int CompareTo(object obj)
            {
                return first.CompareTo((obj as Applicant).first);
            }
        }
 
        static void Main(string[] args)
        {
            int examCount = int.Parse(Console.ReadLine());
 
            //시험 횟수만큼 반복.
            for (int j = 0; j < examCount; j++)
            {
                //지원자 점수를 저장할 리스트.
                var AppList = new List<Applicant>();
 
                //지원자 수
                int appCount = int.Parse(Console.ReadLine());
 
                for(int i = 0; i < appCount; i++)
                {
                    //지원자 숫자만큼 입력 받음.
                    string[] strAppScore = Console.ReadLine().Split(' ');
                    AppList.Add(new Applicant(int.Parse(strAppScore[0]), int.Parse(strAppScore[1])));
 
                }
 
                //지원자가 1명일 때 무조건 합격.
                if (appCount == 1)
                {
                    Console.WriteLine(1);
                    continue;
                }
 
                //지원자들을 첫번째 시험점수 기준으로 정렬
                AppList.Sort();
 
                //시험을 가장 잘본 지원자와 실패한 숫자를 초기화.
                Applicant bestApp = AppList[0];
                int failAppCount = 0;
 
                for(int i = 1; i < appCount; i++)
                {
                    //가장 잘본 사람의 실기 등수 보다 확인하는 사람의 실기 등수가 안좋을 때;
                    if (AppList[i].second > bestApp.second)
                        failAppCount++;
 
                    //실기 등수가 높을 때.
                    else
                        bestApp = AppList[i];
                }
 
                Console.WriteLine(AppList.Count - failAppCount);
            }
        }
    }
}

이를 필기 시험에 대해 오름차순 소트하면 결과는

지원자    필기     면접

3 :          1         3

2 :          2         4

1 :          3         2

4 :          4         1

이와 같이 나오게 됩니다. 3번 지원자는 필기에서 1등을 했으므로 무조건 합격이며 2번 지원자를 보겠습니다.

2번 지원자는 3번 지원자보다 필기 시험을 못봤음이 명백합니다. 그러므로 위의 참가자 중 면접 등수가

본인보다 높은 지원자가 있는지 확인하면 됩니다. 3번 지원자는 2번 보다 면접을 잘 봤기에 2번은

탈락해야 합니다.

 

다음으로 1번 참가자를 보기 전에 위의 참가자 중 면접을 가장 잘 본 지원자를 업데이트 해야 합니다.

1번 참가자는 3, 2번 참가자와 면접 점수를 모두 비교해 봐야 합니다. 필기는 못봤음이 분명하구요.

위의 지원자 중 면접을 가장 잘본 사람을 가지고 있다면 그 지원자만 비교하면 될 것입니다.

 

2번이 3번과 비교할 때 2번이 탈락 했다면 면접 또한 낮은 것이므로 탈락자 수만 하나 올리고 업데이트 하지 않습니다.

2번의 면접 등수가 1번보다 높았다면 탈락하지 않으며 그 면접 점수를 여태 본 지원자 중 가장 면접 점수가 높았던 곳에 업데이트해 가지고 있습니다. 그럼 다음에 보는 1번 지원자는 3, 2번 지원자 보다 필기 등수가 낮으며 면접을 가장 잘 본

2번 사람과만 비교하면 될 것입니다. 이것을 마지막 참가자 까지 반복하면 되겠습니다.