1946-신입사원

 

<문제>

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

1946번: 신입 사원

<풀이>

1.)서류전형순위와 면접전형순위를 record배열에 저장한다.-record[(서류전형순위,면접전형순위)]

2.)서류전형순위를 기준으로 오름차순 정렬한다.-recordd.sort(key=lambda x:x[0])

3.)문제에서 다른 면접자와 비교해서 두 순위 모두  낮으면 탈락이라했고 서류전형순위는 오름차순으로 정렬했으니 면접전형순위를 비교한다.

3)-1. 즉 record[1][1]~record[i][1]을 비교하면 된다.(record[0][1]은 <풀이>2.)에서 서류전형순위가 1위이므로 무조건 합격이다.)

3)-2.  record[i][1]이 합격하기 위해선  record[0][1]~record[i-1][1]중에 순위가 높은 면접자가 한명이라도 있으면 안된다.

        (record[0][1]~record[i-1][1]은 이미 서류전형순위가  record[i][1]보다 높기 때문이다.-<풀이>2.))

 

4)비교방법

4.-1)record[0][1]=Max로 정의한다.

4-2.)record[1][1]~record[i][1]까지 반복문으로 돌면서  Max보다 숫자가 작다면(순위가 높다면)합격으로 판단하고  Max값을   갱신해준다.

 

-파이썬 코드-

import sys
def solution(record):
    answer = 1
    record.sort(key = lambda x:x[0])
    Max = record[0][1]
    for i in range(1,len(record)):
       if Max>record[i][1]:
           answer+=1
           Max = record[i][1]   
            
    return answer

T = int(sys.stdin.readline())
for _ in range(T):
    record = []
    N = int(sys.stdin.readline())
    for _ in range(N):
        n,m = map(int,sys.stdin.readline().split())
        record.append((n,m))
    
    print(solution(record))

※위와 같은 그리디 알고리즘에선 첫번째 값을 초기값으로 저장하고 반복문을 돌면서 특정 기준을 만족했을 때 초기값을 갱신하는 방식의 풀이가 많이 사용된다. 이 방법은 꼭 기억해 두기로 하자.

 

-자바코드-

 

import java.util.*;
import java.io.*;
public class Main{
    public static int solution(int [][] record){
        int answer = 1;
        Arrays.sort(record,Comparator.comparing(o1->o1[0]));
        int Max = record[0][1];
        for(int i=1;i<record.length;i++){
            if(Max>record[i][1]){
                answer++;
                Max = record[i][1];
            }

        }
        return answer;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        Main ac = new Main();
        int T = Integer.parseInt(bf.readLine());
        for(int i =0;i<T;i++){
            int [][] record;
            int N = Integer.parseInt(bf.readLine());
            record = new int[N][2];
            for(int j=0;j<N;j++){
                String str = bf.readLine();
                StringTokenizer st = new StringTokenizer(str);
                int a = Integer.parseInt(st.nextToken()); 
                int b = Integer.parseInt(st.nextToken());
                record[j][0]=a;
                record[j][1]=b;


            }
            int answer = Main.solution(record);
            System.out.println(answer);

        }
        

    }
}