이것저것 개발 블로그

https://www.acmicpc.net/problem/1946

풀이)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Main_BJ_1946_신입사원 {
    public static class person implements Comparable<person>{
        int paper;
        int interview;

        public person(int paper, int interview){
            this.paper = paper;
            this.interview = interview;
        }

        @Override
        public int compareTo(person p){
            return this.paper-p.paper;
        }
    }//person

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int t = Integer.parseInt(br.readLine());
        for(int tc = 0; tc<t; tc++){
            int n = Integer.parseInt(br.readLine());
            ArrayList<person> arr = new ArrayList<>();
            for(int i=0; i<n; i++){
                StringTokenizer st = new StringTokenizer(br.readLine());
                arr.add(new person(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
            }
            Collections.sort(arr);

            // 이미 오름차순 정렬을 했기 때문에, 마지막으로 합격한 사람보다 인터뷰 순위가 작으면 무조건 합격!
            // 서류는 이미 이전사람보다 클 것이고, 인터뷰 순위마저 큰다면 조건에 위배가 된다.

            int ans = 1;
            // 처음은 서류1등 인터뷰 성적
            int min = arr.get(0).interview;
            // 서류 2등 친구부터
            for(int i=1; i<arr.size(); i++){
                // 만약 기준 등수 보다 살펴보는 친구의 등수가 높다면? -> 선발
                // 가장 최근에 채용된 지원자의 면접 순위보다 높은 지원자 찾기
                if(arr.get(i).interview < min){
                    // 기준 등수 갱신
                    min = arr.get(i).interview;
                    // 선발
                    ans++;
                }
            }//for

            // 시간초과 나는 코드
//            for(int i=1; i<arr.size(); i++){
//                for(int j=0; j<i; j++){
//                    if(arr.get(i).interview < arr.get(j).interview){
//                        ans++;
//                        break;
//                    }
//                }
//            }//for
            sb.append(ans+"\n");
        }//tc
        System.out.print(sb);
    }//main
}

진짜 시간초과가 도저히 해결이 안 나서 여러 블로그를 읽어보고...

왜 저렇게 푸는지 생각한 것 같다.

일단... 절대절대 2중 for문 돌려서 해결할 생각 하지 말 것!!!!

시간초과가 난다...(N이 10만이라서 시간 초과 난다)

먼저, 서류 성적 순으로 정렬을 해준다!

Collections.sort는 NlogN으로 정렬을 해주기 때문에 시간초과 걱정은 할 필요 없다.

그리고 기준 변수를 정해주고, 확인하는 방식으로 해야한다.

이때, 변수란 마지막으로 합격한 사람의 인터뷰 성적이다.

이미 오름차순 정렬을 했기 때문에, 마지막으로 합격한 사람보다 인터뷰 순위가 작으면 무조건 합격!!!

서류는 이미 이전 사람보다 클 것이고(등수가 낮을 것이고), 인터뷰 순위마저 크다면 조건에 위배가 된다!

처음에는 이게 무슨소리인가... 했는데,,, 차근차근 보면 안다..

꼭 한 번 깊게 생각해보길ㅠㅠㅠ

어쨌든 이번 문제는,,, 실버1치고는 시간 초과 때문에 힘들었다...

문제 자체는 어렵지 않고, greedy로 할 수 있는 문제!

참고한 블로그...

https://dundung.tistory.com/69

https://dy-coding.tistory.com/entry/%EB%B0%B1%EC%A4%80-1946%EB%B2%88-%EC%8B%A0%EC%9E%85-%EC%82%AC%EC%9B%90-java