백준 1946 신입 사원 Java

문제를 이해하는 것부터 나에겐 시간이 걸렸고 구현하는 데에도 여러 번의 시행착오를 겪었던

그리디 문제인 신입 사원이다.

흔히들 말하는 맞았는데 왜 틀리지.가 자동으로 연발됐던 문제였다.

 

문제를 간단하게 요약하면 지원자가 전부 한자리에 모여있을 때

누군가가 나보다 면접 순위, 서류  둘 다 높으면 절대 붙을 수 없다.

둘 중 하나의 순위라도 다른 지원자들 보다 높아야 한다는 것이다.

 

입력받는 게 순위, 등수가 아니라 점수인 줄 알아서 헷갈렸고

순위인 것을 알아채고도 헷갈렸었다.

 

예제

5

3 2

1 4

4 1

2 3

5 5

에서 3 2의 경우를 보면

1 4 보다 면접 순위가 2 < 4로 낮고

4 1 보다 서류 순위가 3 < 4로 낮고

2 3 보다 면접 순위가 2 < 3으로 낮고

5 5 보다는 둘 다 높다.

그래서 3 2는 합격인 것이다.

 

이런 식으로 최대 합격자를 찾으면 되는데

지원자 수 최대가 100000, 십만에

테스트 케이스가 20까지 있다.

테트 케이스마다 한 명씩 비교해보는 방식인 O(n^2)로 구현해서는 

시간 초과를 절대 해결할 수 없다.

 

서류 순위를 x라고 보고 면접 순위를 y라고 보겠다.

처음에는 x순으로 정렬하고

x가 1인 사람의 y보다 높은 사람을 전부 탈락시키고

탈락 안한 사람들을 따로 모아서 y순으로 정렬하고

y가 1인 사람의 x보다 높은 사람을 전부 탈락시키고

남은 사람의 명 수를 출력했다.

 

완벽하다고 생각했는데 틀렸습니다가 떴다.

입에선 맞았는데 왜 틀리지??????????????라는 말이 자동으로 나오는 도중

반례를 찾았다.

1
6
6 4
4 1
5 2 
1 6
2 3
3 5

내 코드에선 결과가 4로 나오지만

정답은 3이다.

위의 방식으로는 전부 다 거를 수가 없다는 걸 한 번에 알게 해 준 반례이다..

혼자 반례를 찾아내는 사람들은 도대체 어떤 사람들일까. 이것도 연습해야 되는 부분이다.

 

아무튼 정답으로 이끌어준 방식은 이전에 탈락자를 색출해냈던 방식에서

합격자를 색출하는 방식으로 바꾸는 것이였다. 그리고 x순으로 오름차순 정렬했다는 점을 이용하면 된다.

x순으로 정렬을 하면 x가 1인사람은 무조건 합격이다.

그리고 x가 2인사람은 x가 1인 사람보다 y가 작으면 무조건 합격이다.

x는 오름차순으로 정렬이 되어있기 때문에 

마지막으로 합격한 사람보다 y가 큰사람은 합격을 할 수 없다.

x는 자동으로 이전사람보다 크고 y마저 크면 조건에 위배된다.

다시 말해 마지막으로 합격한 사람보다 y가 작은 사람들은 합격이란 소리이다.

이런 식으로 코드를 짜니 성공하였다.

 

이것저것 해보다 보니

원래 임의의 클래스를 하나 만들어서 Comparable인터페이스를 통해 x순 정렬을 했었는데

순위는 중복되지 않기 때문에 그럴 필요 없다는 것도 알게 되었다.

1차원 배열로

a[x] = y 이런 식으로 작성하면 정렬로 인한 nlogn의 시간도 필요 없다.

 

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int tc = Integer.parseInt(reader.readLine());
 
        while(tc-- > 0) {
            int n = Integer.parseInt(reader.readLine());
            int [] a= new int[n+1];
 
            for(int i=0; i<n; i++) {
                StringTokenizer st = new StringTokenizer(reader.readLine());
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                a[x] = y;
            }
            
            int cnt = 1; //x가 1일때는 무조건 가능하므로 1로 시작
            int standard = a[1]; //기준 값, 처음에는 x가 1일 때의 y값
            for(int i=2; i<=n; i++) {
                if(standard > a[i]) { //기준 값보다 a[i]의 y값이 작다면 
                    cnt++; //추가
                    standard = a[i]; //기준 값 a[i]의 y값으로 변경
                }
            }
            System.out.println(cnt);
        }
    }