[백준] 알고리즘 분류(그리디 알고리즘,JAVA)1946번, 신입 사원

문제 링크

1946번: 신입 사원

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 각 지원자들은 서류 점수와 면접 점수의 순위가 주어집니다.

2. 지원자의 두 개의 점수가 모두 다른 지원자보다 순위가 낮은 경우 신입사원이 될 수 없습니다.

3. 신입사원으로 선발할 수 있는 최대 인원을 결과로 출력합니다.

 

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 지원자들의 서류 순위로 정렬한 뒤 면접 순위에 따라 선발 가능한 인원 확인합니다.

 

3. 선발 가능한 인원을 결과로 출력합니다.

 

신입사원.

 

예를 들어.

지원자 1 : 서류(2), 면접(2)

지원자 2 : 서류(1), 면접(1)

 

지원자 1은 지원자 2보다 서류와 면접 순위가 모두 낮기 때문에 신입사원이 될 수 없습니다.

 

지원자들의 2개의 점수 중 1개의 순위를 오름차순 정렬한 뒤에 남은 순위를 통해서 신입사원이 될 수 있는지 확인할 수 있습니다.

	서류	면접
지원자1	3	1
지원자2	2	2
지원자3	1	3

서류 순위로 오름차순 정렬

	서류	면접
지원자3	1	3
지원자2	2	2
지원자1	3	1

 

지원자 3

서류 순위가 1위로써 두 순위 모두 다른 지원자보다 떨어질 일이 없으므로 신입 합격

 

지원자 2

서류 순위는 항상 자신보다 높은 순위가 존재 : 지원자 3

면접은 자신보다 위에 있는 지원자 비교 시 : 더 높은 지원자 X

신입 합격

 

지원자 1

서류 순위는 항상 자신보다 높은 순위가 존재 : 지원자 3

면접은 자신보다 위에 있는 지원자 비교 시 : 더 높은 지원자 X

신입 합격

 

예제입력 1.

※1번째 테스트 케이스만 진행하는 과정을 보여드리겠습니다.

 

1. 입력된 정보를 저장합니다.

 

 N : 5

	서류	면접
지원자1	3	2
지원자2	1	4
지원자3	4	1
지원자4	2	3
지원자5	5	5

 

2. 지원자들의 서류 순위로 정렬한 뒤 면접 순위에 따라 선발 가능한 인원 확인합니다.

 

지원자 오름차순 정렬

 

	서류	면접
지원자2	1	4
지원자4	2	3
지원자1	3	2
지원자3	4	1
지원자5	5	5

순위 비교.

 

지원자 2 

서류 순위가 1위로써 두 순위 모두 다른 지원자보다 떨어질 일이 없으므로 신입 합격

 

지원자 4

서류 순위는 항상 자신보다 높은 순위가 존재 : 지원자 2

면접은 자신보다 위에 있는 지원자 비교 시 : 더 높은 지원자 X

신입 합격

 

지원자 1

서류 순위는 항상 자신보다 높은 순위가 존재 : 지원자 2

면접은 자신보다 위에 있는 지원자 비교 시 : 더 높은 지원자 X

신입 합격

 

지원자 3

서류 순위는 항상 자신보다 높은 순위가 존재 : 지원자 2

면접은 자신보다 위에 있는 지원자 비교 시 : 더 높은 지원자 X

신입 합격

 

지원자 5

서류 순위는 항상 자신보다 높은 순위가 존재 : 지원자 2

면접은 자신보다 위에 있는 지원자 비교 시 : 더 높은 지원자 2, 4, 1, 3

신입 불합격

 

3. 선발 가능한 인원을 결과로 출력합니다.

 

4명을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer을 이용하여 지원자들의 점수를 띄어쓰기로 나누었습니다.
• Collections.sort를 이용하여 지원자들의 서류 순위 별 오름차순 정렬하였습니다.
• 각 지원자에서 자신보다 서류 순위가 높은 지원자와 면접 순위를 비교합니다.
• 면접 순위가 높은 지원자가 존재하면 신입 불합격, 없으면 신입 합격입니다.
• 신입 합격한 지원자의 수를 BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

 

import java.io.*;
import java.util.*;


public class Main {
    //지원자 점수 관련 클래스
    static class score implements Comparable<score>{
        int documentScore, interviewScore;
        public score(int dScore, int iScore){
            documentScore = dScore;
            interviewScore = iScore;
        }
        //지원자 정렬 시 서류 점수로 오름차순 정렬 정의
        @Override
        public int compareTo(score o) {
            return this.documentScore - o.documentScore;
        }
    }
    public static void main(String[] args) throws IOException{
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        int T = Integer.parseInt(br.readLine());
        //각 테스트 케이스 진행
        for(int i=0;i<T;i++){
            int N = Integer.parseInt(br.readLine());
            ArrayList<score> list = new ArrayList<>();
            //지원자들 점수 저장
            for(int j=0;j<N;j++){
                st = new StringTokenizer(br.readLine()," ");
                int score1 = Integer.parseInt(st.nextToken());
                int score2 = Integer.parseInt(st.nextToken());
                list.add(new score(score1, score2));
            }
            //지원자 서류 순위로 오름차순 정렬
            Collections.sort(list);
            int answer = 1;
            //서류 순위 오름차순에서 면접 순위가 높은 값 저장
            int min = list.get(0).interviewScore;
            //각 지원자들 서류 순위 더 높은 지원자들 면접 순위 비교
            for(int j=1;j<N;j++){
                //면접 순위가 현재 최소 순위보다 높을 때
                if(list.get(j).interviewScore < min){
                    min = list.get(j).interviewScore;
                    answer++;
                }
            }
            bw.write(answer + "\n");	//합격 인원 BufferedWriter 저장
        }
        bw.flush();		//결과 출력
        bw.close();	
        br.close();
    }
}