[Java] 백준 1946 : 신입 사원

문제 링크

1.

노트에 좀 끄적이다가 아이디어가 떠올라 코드를 쭉 썼다.

아무 생각 없이 제출했으나 시간 초과..

 

나는 list를 이용해서 서류 성적을 기준으로 정렬하고 list를 순회하며 값을 비교하기 위해 이중 for문을 사용하였다.

하지만, 이중 for문을 사용하면 $O(N^{2})$ 인데 지원자의 최대 수가 $100,000$ 이므로 시간 초과가 날 수밖에 없다.

 

결국 이중 for문을 사용하지 않는 방법을 찾아야 하는데 찾지 못해 풀이를 참고하였다.

 

 

2.

그 방법은 생각보다 단순했다.

두 성적 순위는 모두 1위부터 N위까지 동석차 없이 결정된다고 가정한다.

 

문제에서, 동석차가 없다고 하였으므로 사용자 정의 Class를 만들 필요 없이 배열의 인덱스 값을 석차로 설정하면 된다! 그러면 성적 정렬을 할 필요도 없어진다.

 

 

문제의 예시를 입력하면 다음과 같이 배열이 만들어진다.

 

서류 성적이 2등인 사람을 생각해보자.

이 사람은 서류 성적 1등인 사람에게 서류 성적을 졌으므로, 면적 성적에서 만큼은 이겨야 선발될 것이다.

하지만, 면접 성적은 5등으로 그 사람에게 서류 성적도 졌고 면접 성적도 졌기에 선발되지 않는다.

 

이러한 메커니즘으로 배열을 한 번만 순회하며 합격자를 선발한다.

이해가 되지 않는다면 문제의 조건인 다음을 다시 한번 읽어보자.

어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류 심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않는다.

 

 

3.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);

        int testCase = sc.nextInt();
        for (int t = 0; t < testCase; t++) {
            int n = sc.nextInt();
            int[] person = new int[n + 1];

            for (int i = 0; i < n; i++) {
                int rankA = sc.nextInt();
                int rankB = sc.nextInt();
                person[rankA] = rankB;
            }

            int cnt = 1;
            int rankB = person[1];
            for (int i = 2; i <= n; i++) {
                if (rankB > person[i]) {
                    rankB = person[i];
                    cnt++;
                }
            }

            System.out.println(cnt);
        }

        sc.close();
    }
}

 

 

4.

동석차가 없다고 하였으므로 배열 인덱스 값을 석차로 설정하는 아이디어..

 

[참고] https://kosaf04pyh.tistory.com/113