백준 : 신입 사원 (1946)

*** 본 풀이는 java언어를 사용하였습니다 ***

문제 보러가기

 

요약

서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발

위 말은 A 지원자의 서류심사 성적이 B 지원자의 서류심사 성적보다 낮더라도 A 지원자의 면접시험 성적이 더 높다면

A 지원자가 선발 된다는 말이다.

 

풀이

다음 예시를 보자.

3 2
1 4
4 1
2 3
5 5

 

지원자들의 성적이 다음과 같이 들어왔다면,

비교를 위해 먼저 성적을 서류심사 순으로 오름차순 정렬한다.

1 4
2 3
3 2
4 1
5 5

 

맨 처음 지원자는 서류심사가 1등.

즉, 적어도 하나가 다른 지원자 보다 떨어 질 수 없는 조건이므로 무조건 합격이다.

서류심사 기준 오름차순 정렬 상태 이므로 다음 지원자는 무조건 서류심사 점수가 처음 지원자보다 낮다.

따라서 면접시험 성적으로 승부를 봐야한다.

처음 지원자의 면접시험 성적이 4이므로, 다음 지원자의 면접시험 성적은 4보다 잘나와야 합격이다.

 

두번째 지원자의 면접시험 성적은 3이므로, 조건에 만족하여 합격이다.

여기서 기준점이 두번째 지원자의 면접시험 성적으로 바뀌는 것에 주의한다.

따라서 면접시험 성적의 기준 점수는 3보다 잘나와야 합격이다.

 

이런식으로 값을 비교해가며 푼다면 문제를 쉽게 풀 수 있을 것이다.

 

제출 코드

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int count = Integer.parseInt(br.readLine());
        for (int i = 0; i < count; i++) {
            int applicantCount = Integer.parseInt(br.readLine());
            List<employer> employers = new ArrayList<>();
            for (int j = 0; j < applicantCount; j++) {
                int[] tokens = Arrays.stream(br.readLine().split(" "))
                                     .mapToInt(Integer::parseInt)
                                     .toArray();
                employers.add(new employer(tokens[0], tokens[1]));
            }
            bw.write(String.valueOf(Solution.solution(employers)));
            bw.newLine();
        }
        bw.flush();
    }
}

class Solution {
    public static int solution(List<employer> employers) {
        employers.sort(Comparator.comparingInt(employer::getDocumentRank));
        int maxPersonCount = 1;
        int standardInterviewRank = employers.get(0).getInterviewRank();
        for (int i = 1; i < employers.size(); i++) {
            employer employer = employers.get(i);
            if (employer.isHigherThanInterviewRank(standardInterviewRank)) {
                maxPersonCount++;
                standardInterviewRank = employer.getInterviewRank();
            }
        }
        return maxPersonCount;
    }
}

class employer {
    private int documentRank;
    private int interviewRank;

    public employer(int documentRank, int interviewRank) {
        this.documentRank = documentRank;
        this.interviewRank = interviewRank;
    }

    public boolean isHigherThanInterviewRank(int standardInterviewRank) {
        return interviewRank < standardInterviewRank;
    }

    public int getDocumentRank() {
        return documentRank;
    }

    public int getInterviewRank() {
        return interviewRank;
    }
}

 

테스트 코드

import org.junit.Before;
import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

import static org.assertj.core.api.Assertions.assertThat;

public class SolutionTest {
    private List<employer> employers;

    @Before
    public void setUp() throws Exception {
        employers = new ArrayList<>();
    }

    @Test
    public void testCase_1() {
        employers.add(new employer(3, 2));
        employers.add(new employer(1, 4));
        employers.add(new employer(4, 1));
        employers.add(new employer(2, 3));
        employers.add(new employer(5, 5));

        assertThat(Solution.solution(employers)).isEqualTo(4);
    }

    @Test
    public void testCase_2() {
        employers.add(new employer(3, 6));
        employers.add(new employer(7, 3));
        employers.add(new employer(4, 2));
        employers.add(new employer(1, 4));
        employers.add(new employer(5, 7));
        employers.add(new employer(2, 5));
        employers.add(new employer(6, 1));

        assertThat(Solution.solution(employers)).isEqualTo(3);
    }

    @Test
    public void testCase_3() {
        employers.add(new employer(1, 1));
        employers.add(new employer(2, 4));
        employers.add(new employer(3, 2));
        employers.add(new employer(4, 3));

        assertThat(Solution.solution(employers)).isEqualTo(1);
    }

    @Test
    public void testCase_4() {
        employers.add(new employer(6, 4));
        employers.add(new employer(4, 1));
        employers.add(new employer(5, 2));
        employers.add(new employer(1, 6));
        employers.add(new employer(2, 3));
        employers.add(new employer(3, 5));

        assertThat(Solution.solution(employers)).isEqualTo(3);
    }
}

 

회고

처음 풀때는 다음과 같이 풀어서 테스트에서 실패했다.

다음과 같이 지원자가 있다고 가정한다.

6 4
4 1
5 2
1 6
2 3
3 5

 

지원자의 서류심사 성적이 1등인 지원자의 면접심사 성적과

지원자의 면접심사 성적이 1등인 지원자의 서류심사 성적은 다음과 같다.

지원자의 서류심사 성적이 1등인 면접심사 성적 : 6
지원자의 면접심사 성적이 1등인 서류심사 성적 : 4

 

따라서 기준점을 단순하게 서류심사 성적이 4 보다 높고, 면접심사 성적이 6보다 높으면 합격으로 정의해버리고 풀었다.

위 식대로 풀면 합격 지원자는 다음과 같다.

4 1
1 6
2 3
3 5

 

이번에는 똑같은 문제를 정답 풀이법으로 풀어보자.

먼저 서류심사 순으로 오름차순 정렬하면 다음과 같다.

1 6
2 3
3 5
4 1
5 2
6 4

 

이후 풀이법은 생략한다. (정답 풀이법 참조)

합격 지원자는 다음과 같다.

1 6
2 3
4 1

 

이러한 차이가 발생하여 테스트에서 실패했던 것..

탐욕법(그리디) 문제를 풀다보면 정렬을 해야할 상황이 많이 나오는 것 같다.

해당 문제를 너무 쉽게 접근하려다 보니 예상치 못한 오류를 범했는데, 다음에는 좀 더 신중하게 문제를 풀어야겠다.