[백준] 1946 신입사원

www.acmicpc.net/problem/1946

1946번: 신입 사원

2020-12-06

---

import java.util.Scanner;
 
public class Main1946 {
    public static int answer, N, arr[];
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int test = sc.nextInt();
        for(int ts = 1; ts <= test; ts++) {
            answer = 0;
            N = sc.nextInt();
            arr = new int[N+1];
            for(int i = 0; i < N; i++) {
                int a = sc.nextInt();
                int b = sc.nextInt();
                arr[a] = b;
            }
            
            int num = 987654321;
            
            for(int i = 1; i <= N; i++) {
                if(num > arr[i]) {
                    num = arr[i];
                    answer++;
                }
            }
            
            System.out.println(answer);
        }
    }
}

 

#문제 풀이

1. 1차원 배열로 입력 값을 받는다. 서류 점수를 배열의 인덱스 값으로, 면접 순위를 값으로 받았다. 이렇게 되면 자연스럽게 정렬을 하지 않아도, 서류 점수가 낮은 순부터 체크를 할 수 있게 된다. 

 

2. 서류 점수는 오름차순으로 정렬이 된 상태이다. 큰 값(num) 을 지정해놓고 면접의 등수와 비교하면서, 면접의 등수가 기준 값보다 더 작은 경우(높은 경우) 선발 가능한 신입사원으로 생각하면 된다.

 

 

#체크 포인트

1. 시간 초과

- 2차원 배열 형태로 [i][0]은 서류 점수, [i][1]은 면접 순위로 받아서 compartor로 정렬을 했었다. 이렇게 하니 시간 초과가 났었다. 생각해보니 면접 점수나 순위 모두 1 <= x <= N 범위 안에서 받아지는 것을 볼 수 있다. 1차원 배열의 index 값으로 받아도 충분히 해결할 수 있었다.

 

2. 문제 입력 값

- 문제 입력 값을 잘못 읽었었다.

둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성적, 면접 성적의 순위가 공백을 사이에 두고 한 줄에 주어진다.

라고 되어 있는데 면접 순위가 아니라 점수로 봐서 한참을 헤맸었다.