1946번 신입사원

코딩테스트 : 1946번 신입사원

신입 사원

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

256 MB

72532

26130

19009

34.389%

문제

언제나 최고만을 지향하는 굴지의 대기업 진영 주식회사가 신규 사원 채용을 실시한다. 인재 선발 시험은 1차 서류심사와 2차 면접시험으로 이루어진다. 최고만을 지향한다는 기업의 이념에 따라 그들은 최고의 인재들만을 사원으로 선발하고 싶어 한다.

그래서 진영 주식회사는, 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙을 세웠다. 즉, 어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류 심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않는다.

이러한 조건을 만족시키면서, 진영 주식회사가 이번 신규 사원 채용에서 선발할 수 있는 신입사원의 최대 인원수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성적, 면접 성적의 순위가 공백을 사이에 두고 한 줄에 주어진다. 두 성적 순위는 모두 1위부터 N위까지 동석차 없이 결정된다고 가정한다.

출력

각 테스트 케이스에 대해서 진영 주식회사가 선발할 수 있는 신입사원의 최대 인원수를 한 줄에 하나씩 출력한다.

using System.Text;

public class BackJoon
{
    public static void Main()
    {
        
        // 테스트 케이스 하나씩마다 새 Dictionary를 생성
        // 모든 결과를 기록 -> 두 개를 생성해야 하는 것인가 ? 100,000개면 메모리는 ㄱㅊ을듯 ? 
        // 다시 처음부터 하나씩 읽어가면서 다음과 같은 비교를 수행
        // 1. 첫 번째 Dictionary에서 서류 심사 순위가 자신의 순위보다 높은 사람 들을 모두 순회하면서 
        // 면접 심사 순위도 높다면 다음으로 넘어가고, 아니라면 Count ++ ;
        // 순회가 끝나면 총 Count 작성 (SB에 저장 ) 
        
        //이렇게 보니까 Dictionary도 하나만 필요하넹 
        
        
        int totalTestCase = int.Parse(Console.ReadLine());
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < totalTestCase; i++)
        {
            int n = int.Parse(Console.ReadLine());

            Dictionary<int,int> dic = new Dictionary<int,int>();
            for (int j = 0; j < n; j++)
            {
                int[] arr = Console.ReadLine().Split().Select(int.Parse).ToArray();
                dic.Add(arr[0], arr[1]);
            }

            int count = 0; 
            // Dictionary에 들어 있는 모든 것들을 하나씩 순회하면서 
            foreach (KeyValuePair<int, int> kvp in dic)
            {
                // 하나를 기준으로 잡고 , 나머지를 돌림 
                bool isFail = false;
                foreach( KeyValuePair<int,int> kvp2 in dic)
                {
                    // 같으면 다음비교로 넘어감 
                    if (kvp.Key == kvp2.Key) continue;
                 if (kvp.Key < kvp2.Key &&  kvp.Value < kvp2.Value) isFail = true;
                }
                if (!isFail) count++;
            }
            sb.AppendLine(count.ToString());
            
        }
        Console.WriteLine(sb.ToString());
         
    }
    


}

 

처음에 작성했던 코드이다. 이 코드는 결과가 틀리는 문제도 있지만, 시간 복잡도 측면에서도 심각한 문제가 있다.
한 테스트 케이스의 최대 지원자 수는 100,000명인데, 이 로직은 O(n²)으로 약 100억 번의 연산이 필요하다. 이는 시간 초과를 일으킨다.
애초에 O(n²)로 구현하면 안 되지만, 최소한 아래 부분은 고칠 수 있다.
isFail이 true가 되면 그 이후 반복은 의미가 없다. 따라서 불필요한 반복을 줄일 수 있다.
게다가 완전 탐색이라고 해도, 이 코드로는 정답이 나오지 않는다.
현재 비교 구문은 다음과 같다:

if (kvp.Key < kvp2.Key &&  kvp.Value < kvp2.Value) isFail = true;

 

하지만 서류 순위와 면접 순위 모두 숫자가 작을수록 좋은 값이므로, 비교 부등호가 반대로 되어야 한다.

 

using System.Text;

public class BackJoon
{
    public static void Main()
    {
        
        int totalTestCase = int.Parse(Console.ReadLine());
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < totalTestCase; i++)
        {
            int n = int.Parse(Console.ReadLine());

            SortedDictionary<int, int> dic = new SortedDictionary<int, int>();
            int count = 0;
            for (int j = 0; j < n; j++)
            {
                int[] arr = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
                dic.Add(arr[0], arr[1]);
            }
            int minSecond = int.MaxValue;

            foreach (KeyValuePair<int, int> pair in dic)
            {
                if (pair.Value < minSecond)
                {
                    count++;
                    minSecond = pair.Value;
                }
            }

            sb.AppendLine(count.ToString());
        }

        Console.WriteLine(sb.ToString());
    }
}

 

결국 풀게 된 코드이다. 이 코드에서 중요한 점은 시간 복잡도를 줄이기 위해 미리 정렬하여, 비교해야 할 변수를 하나로 줄였다는 점이다.
이렇게 하면 시간 복잡도는 정렬에 걸리는 시간 + 순회 한 번이므로 매우 효율적이다.
시간 복잡도가 신경 쓰일 때는, 비교해야 할 변수의 수를 줄일 수 있는 방법을 우선적으로 고민해봐야 한다. 그중 대표적인 방법이 정렬이다.
추가로, SortedDictionary를 사용할지, Dictionary로 받고 한 번에 정렬할지 고민했는데, 후자가 더 낫다고 한다.
SortedDictionary는 매 삽입마다 균형을 유지하느라 자원이 더 소모되기 때문이다.