<Algorithm> 31. 1946번 신입사원

1. 1946번 신입사원

• 그리디 알고리즘 -> 매번 비교를 통해 가장 최선이 되는 값을 구한다.

• 처음에는 모든 경우의 수를 판단해서 한명씩 지워나가게 했으나 사원수가 최대 100000 명이므로 시간 초과 발생

• 배열의 인덱스를 이용하여 쉽게 순위를 판단하여 풀 수 있는 문제 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.Collection; import java.util.Collections; import java.util.Comparator; import java.util.StringTokenizer;   public class Main {     public static void main(String[] args) throws NumberFormatException, IOException {         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         StringTokenizer st;         int T = Integer.parseInt(br.readLine());         ArrayList<Object> ans = new ArrayList<Object>();                  for(int k = 0; k < T; k++) {             int people = Integer.parseInt(br.readLine());             int count = 0;             int[] score = new int[people + 1];                          for(int i = 0; i < people ; i++) {                 st = new StringTokenizer(br.readLine());                                 int x = Integer.parseInt(st.nextToken());                 int y = Integer.parseInt(st.nextToken());                 score[x] = y; // 배열을 이용하여 서류 등수를 알수 있다.             }             int std = score[1];// 1등의 면접 순위를 기준으로 설정                          for(int i = 2; i <= people; i++) {                 if(std > score[i]) {                     std = score[i]; // 기준을 변경한다                     count ++; // 선발                 }             }                          ans.add(count + 1); // 1등 카운트         }                  for(Object obj:ans)             System.out.println(obj);              }      }   /*public class Main {     static int count;     static boolean visited[];     public static void main(String[] args) throws NumberFormatException, IOException {         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         StringTokenizer st;         int T = Integer.parseInt(br.readLine());         ArrayList<Object> ans = new ArrayList<Object>();                  for(int k = 0; k < T; k++) {             int people = Integer.parseInt(br.readLine());             count = people;             visited = new boolean[100000];                          Score[] score = new Score[people];                          for(int i = 0; i < people ; i++) {                 st = new StringTokenizer(br.readLine());                                 int x = Integer.parseInt(st.nextToken());                 int y = Integer.parseInt(st.nextToken());                 score[i] = new Score(x, y);                      }                          compare(score, 0);             ans.add(count);          }                  for(Object obj:ans)             System.out.println(obj);              }     public static void compare(Score[] score, int index, int comp) {                  if(index == score.length) return;                      for(int i = 0; i < score.length; i++) {                 if(visited[i]) continue;                                  int x = score[index].x;                 int y = score[index].y;                                  if(score[i].x < x && score[i].y < y) {                     count--;                     visited[index] = true;                     break;                 }else if(score[i].x > x && score[i].y > y) {                     visited[i] = true;                 }              }         compare(score, index + 1);     }      } class Score{     int x;     int y;          public Score(int x, int y) {         this.x = x;         this.y = y;     } } */ Colored by Color Scripter

cs