BOJ) 신입 사원

신입 사원

1946번: 신입 사원

풀이

 

처음에는 완전탐색으로 풀려고 시도했다.

하지만, 모든 배열을 n번씩 돌다보니까 시간초과가 떴다.

그래서 정렬을 이용해야 겠다고 생각했다.

 

정렬의 기준을 잡는데 고민을 많이 했는데, 서류와 면접 둘 다 포함시켜 정렬하기엔 너무 복잡해서 하나를 기준으로 정렬을 해야겠다고 생각했다.

그래서, 서류 심사를 기준으로 오름차순 정렬을 해줬다.

 

서류 심사에서 1등을 받은 사람의 면접 등수를 첫 기준으로 삼고, 서류 2등부터 쭉 돌면서 면접 등수가 1등보다 높은 사람을 찾았다.

면접 등수가 높은 사람은 서류에서 등수가 낮더라도 채용 기준에 부합하기 때문에 count+1을 해줬다.

다음 탐색부터는 이 사람의 면접 등수를 기준으로 더 빠른 지원자를 찾아나갔다.

 

코드 1

 

통과는 했지만 메모리와 속도가 너무 심각했다.

어떻게 할지 고민하다가, 어차피 서류를 기준으로 정렬을 할거면, 2차원 배열말고 1차원 배열로 선언하는 것이 좋다고 생각했다.

서류 1등의 index는 1이 되게, 그리고 이 사람의 면접 등수가 value가 되게 배열을 저장했다.

이렇게 되면, 정렬하는데 들어가는 비용을 많이 줄일 수 있다고 생각했다.

 

코드 2

메모리와 시간이 현저하게 준 것을 확인할 수 있었다.

 

 

코드 1

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        solution(new BufferedReader(new InputStreamReader(System.in)));
    }

    private static void solution(BufferedReader br) throws IOException {
        int testCase = Integer.parseInt(br.readLine());
        final String NEWLINE = "\n";
        StringBuffer sb = new StringBuffer();
        for(int i=0; i<testCase; i++) {
            int n = Integer.parseInt(br.readLine());
            int[][] participants = new int[n][2];
            for(int j=0; j<n; j++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                participants[j][0] = Integer.parseInt(st.nextToken());
                participants[j][1] = Integer.parseInt(st.nextToken());
            }
            sb.append(getFreshMan(n,participants)).append(NEWLINE);
        }
        System.out.println(sb.toString());
    }

    private static int getFreshMan(int n, int[][] participants) {
        final int DOCUMENT =0, INTERVIEW =1;
        int result =1;
        Arrays.sort(participants, (int[] o1, int[] o2) -> o1[DOCUMENT] > o2[DOCUMENT] ? 1:-1); // 서류 심사 오름차순 정렬
        int min = participants[DOCUMENT][INTERVIEW];
        for(int i=1; i<n; i++) {
            if(min > participants[i][INTERVIEW]) {
                result++;
                min = participants[i][INTERVIEW];
            }  
        }
        return result;
    }
}

 

코드 2

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        solution(new BufferedReader(new InputStreamReader(System.in)));
    }

    private static void solution(BufferedReader br) throws IOException {
        int testCase = Integer.parseInt(br.readLine());
        final String NEWLINE = "\n";
        StringBuffer sb = new StringBuffer();
        for(int i=0; i<testCase; i++) {
            int n = Integer.parseInt(br.readLine());
            int[] participants = new int[n+1];
            for(int j=0; j<n; j++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                participants[Integer.parseInt(st.nextToken())] = Integer.parseInt(st.nextToken());
            }
            sb.append(getFreshMan(n,participants)).append(NEWLINE);
        }
        System.out.println(sb.toString());
    }

    private static int getFreshMan(int n, int[] participants) {
        final int FIRST =1;
        int result =FIRST;
        int min = participants[FIRST];
        for(int i=2; i<=n; i++) {
            if(min > participants[i]) {
                result++;
                min = participants[i];
            }  
        }
        return result;
    }
}