[알고리즘풀이]백준 1946 : 신입 사원 JAVA

목차

• 개요
•  본문
•  1) 문제
•  2) 과정
•  3) 코드 전체

 

 

개요

이전에 알고리즘 스터디에서 JAVA를 이용해 백준 1946번 신입 사원을 풀었습니다. 이를 정리해보고자 합니다.

1946번: 신입 사원

 

본문

1) 문제

2) 과정

푸는 시간은 2시간 조금 넘게 걸렸던 문제입니다. 이번 문제를 풀며 사용한 아이디어는 다음과 같습니다.

서류와 면접 성적이 모두 떨어진다면 선발되지 않는다의 의미는 둘 중 하나라도 떨어지지 않으면 선발된다. 를 의미합니다. 때문에 아래와 같이 탈락과 합격이 결정되게 되는데요.

doc(서류) 부족 + itv(인터뷰) 부족 => 탈락 doc(서류) 충족 + itv(인터뷰) 부족 => 합격 doc(서류) 부족 + itv(인터뷰) 충족 => 합격 doc(서류) 충족 + itv(인터뷰) 충족 => 합격

즉, doc의 1등보다 itv가 크거나 itv의 1등보다 doc이 크면 살아남습니다.

이를 이용해 doc 1등의 itv 등수보다 itv에서 값이 높은 애들을 비교하는 방식으로 문제를 풀었습니다.

 

2-1) main

    public static void main(String[] args) throws IOException {
    	// Input - case횟수 받기
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int cases = Integer.parseInt(reader.readLine());
		
        // Input - 지원자들의 수와 서류와 면접 등수 받기
        for(int i=0;i<cases;i++){
            int n=Integer.parseInt(reader.readLine()); // 지원자수
            int[] scoreArr = new int[n+1];
            for (int j = 0; j < n; j++) {
                String[] strArr = reader.readLine().split(" ");
                int doc=Integer.parseInt(strArr[0]);
                int itv=Integer.parseInt(strArr[1]);
                scoreArr[doc]=itv;
            }
            
            // Logic
            int answer = 1; // doc 1등은 미리 선정됐기에 1로 시작
            int standardItv = scoreArr[1];
            for(int k=2; k<=n;k++){
                if(scoreArr[k]<standardItv){
                    answer++;
                    standardItv=scoreArr[k];
                }
            }
            
            // Output
            System.out.println(answer);
        }
    }

Input과 Output은 다들 익숙하실 거라 생각해 Logic부분만 간단히 설명해보도록 하겠습니다.

 

변수 몇가지를 정의한다면, answer은 선발할 수 있는 최대 신입사원의 수를 담을 변수이고, scoreArr의 구조는 doc을 인덱스로 사용하고 itv를 해당 인덱스의 값으로 이뤄졌기 때문에 standardItv는 scoreArr[1], 즉 doc 1등의 itv 점수를 미리 지정해줍니다.

 

for문을 통해 2등부터 모든 지원자수를 돌며 doc 1등의 인터뷰 등수보다 높다면(scoreArr[k]<standardItv) 선발할 수 있는 신입사원의 수(answer)을 1개 증가시키고, 기준 등수(standardItv)를 현재 지원자의 인터뷰 점수로 바꿔줍니다. 이렇게 내려가다보면 서류와 인터뷰 모두에서 심하게 뒤쳐지지 않는 신입사원만 선발할 수 있습니다.

 

 

3) 전체코드

그렇게 완성된 코드는 다음과 같습니다.

package sujeong.greedy;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class BOJ1946 {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        int cases = Integer.parseInt(reader.readLine());

        for(int i=0;i<cases;i++){
            int n=Integer.parseInt(reader.readLine()); // 지원자수
            int[] scoreArr = new int[n+1];
            for (int j = 0; j < n; j++) {
                String[] strArr = reader.readLine().split(" ");
                int doc=Integer.parseInt(strArr[0]);
                int itv=Integer.parseInt(strArr[1]);
                scoreArr[doc]=itv;
            }
            int answer = 1; // doc 1등은 미리 선정됐기에 1로 시작
            int standardItv = scoreArr[1];
            for(int k=2; k<=n;k++){
                if(scoreArr[k]<standardItv){
                    answer++;
                    standardItv=scoreArr[k];
                }
            }
            System.out.println(answer);
        }
    }
}

 

깃헙으로 더 자세히 보고싶으시다면, 아래 링크를 참고해주세요 :)

https://github.com/Park1122/Algorithm-Study/blob/master/sujeong/greedy/BOJ1946.java

GitHub - Park1122/Algorithm-Study: 명지대학교 학생들이 모여서 만든 알고리즘 공부 및 코딩테스트 준비