[백준 Java] 1946 신입사원 실버1 , 그리디

🔗 문제링크 🔗

1946번: 신입 사원

---

🌟 생각 흐름 🌟

먼저 이 문제는 순위로 표기하므로 높은 점수가 아닌 낮은 점수가 우선순위가 높다.

문제는 내가 모든 지원자들보다 1,2차 점수중 하나의 순위라도 더 좋아야(낮아야) 한다는 것이다.

 

1 Try (시간 초과)  : 단순 그리디 문제로 생각하고 접근했다. 1차 점수 기준으로 정렬을 한다. 즉 정렬된 후에 앞에 있는 사람들이 현재 자신보다 무조건 1차 점수는 높은 것(순위는 낮은 것)이다. 따라서 앞에 있는 모든 사람들 보다 2차 점수가 높아야(순위가 낮아야) 신입사원이 될 수 있다. 그래서 포문으로 앞에 있는 것을 모두 돌았다

 

생각해 보니 계속 앞에 있는 걸 확인할 필요는 없다는 생각을 했다 어차피 앞에 있는 사람들 중 순위가 가장 낮은 사람보다 현재 나(i)의 순위가 낮아야만 내가 신입사원으로 입사할 수 있다. 

 

2 Try (통과, 317168KB, 3156ms): 1차 점수기준 정렬 후에 만약 앞에 있는 사람의 2차 순위 보다 나의 순위가 더 작으면(더 잘한 것) 나는 신입사원이 될 수 있고 뒤에 있는 사람의 2차 점수는 나의 순위보다 낮아야 하므로 minRank 더 낮을 순위로 갱신한다 -> 통과 -> 그런데 다른 사람들의 소요시간이 훨씬 적었다 뭔가 다른 풀이가 있을 것 같아 생각하다 보니 문제에서 순위는 중복되지 않는다라고 적혀있음이 번뜩 생각났다 

 

3 Try (통과, 298440KB, 804ms): " arr [1차 점수 순위의 값] =  2차 점수 순위의 값 "을 넣으면 앞에 순위의 있는 사람의 2차 점수의 최소 순위보다 현재 나의 2차 점수의 최소 순위가 낮으면 되므로 2 Try 방법과 동일하게 풀이할 수 있다. 이렇게 하면 배열도 1차원으로 해결가능하고 정렬도 하지 않아도 되므로 더욱 효율적이다.

 

문제를 보면 일단을 주먹구구식으로 풀고 시간 초과 안 나면 그냥 넘어가는 스타일이 되어버렸는데 최적화 방법을 생각하는 습관을 들여야겠다.

---

🍳 코드 🍳

 

2 Try (통과, 317168KB, 3156ms):

package 백준.greedy;

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

public class boj_1946_신입사원_기본풀이 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        int tc = Integer.parseInt(br.readLine());
        while (tc-- > 0) {
            int n = Integer.parseInt(br.readLine());
            int[][] arr = new int[n][2];
            for (int i = 0; i < n; i++) {
                st = new StringTokenizer(br.readLine());
                arr[i][0] = Integer.parseInt(st.nextToken());// 시험 성적의 순위
                arr[i][1] = Integer.parseInt(st.nextToken());//면접 성적의 순위
            }

            //면접 순위 별로(오름차순)
            Arrays.sort(arr, Comparator.comparingInt(o -> o[0]));

            int cnt = 1; // 1차 서류 심사 결과 점수가 제일 높은 사람은 무조건 통과임
            int minRank = arr[0][1]; //어차피 앞에서 2차 점수의 제일 순위 낮은 사람하고만 비교하면 된다.
            if (n > 1) { //한명인 경우는 무조건 한명임
                for (int i = 1; i < n; i++) {
                    if (minRank > arr[i][1]) {
                        minRank = arr[i][1];
                        cnt++;
                    }
                }
            }
            sb.append(cnt).append("\n");
        }
        System.out.println(sb);
    }
}

3 Try (통과, 298440KB, 804ms): 

package 백준.greedy;

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

public class boj_1946_신입사원_최적화 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        int tc = Integer.parseInt(br.readLine());
        while (tc-- > 0) {
            int n = Integer.parseInt(br.readLine());
            if (n == 1) {//한명인 경우는 무조건 1
                sb.append(1).append("\n");
                continue;
            }

            int[] arr = new int[n + 1];
            for (int i = 0; i < n; i++) {
                st = new StringTokenizer(br.readLine());
                //어차피 우선순위는 중복되지 않기 떄문에 가능
                arr[Integer.parseInt(st.nextToken())] = Integer.parseInt(st.nextToken());//2차 면접의 우선순위
            }

            int cnt = 1;
            int minRank = arr[1];
            for (int i = 2; i <= n; i++) {
                if (minRank > arr[i]) {
                    minRank = arr[i];
                    cnt++;
                }
            }
            sb.append(cnt).append("\n");
        }
        System.out.println(sb);
    }
}