[백준 - 1946번] 신입사원 - Java //Wello Horld//

이번에는 백준알고리즘 1946번 신입사원 문제를 풀어보도록 하자

먼저 테스트 케이스 T가 주어지고 각 테스트 케이스마다 면접을 본 지원자의 수 N이 주어진다. 그 다음줄 부터 지원자들의 서류심사와 면접시험의 결과가 등수로 나오게 되는데, 그 등수를 이용해서 뽑힐 수 있는 신입사원의 최대 인원 수를 구하는 프로그램을 작성하면 된다.

이 문제를 풀 때 주의해야 될 점은, 테스트 케이스의 개수가 20 까지이고, 지원자의 숫자가 N이므로 반복문 만으로 풀면 시간초과가 뜰 것이 자명하다. 하여, 이번 문제를 풀때에, 쉽게 key값과 value 값을 지정할 수 있는 HashMap을 이용해서 문제를 풀었다. 먼저, HashMap을 두개 사용하여, 서류심사 등수를 key 값으로하는 HashMap, 면접시험 등수를 key값로 하는 HashMap 두개를 만들고, 서류심사 등수가 1등인 사람의 면접시험 등수를 secondLimit으로, 면접시험 등수가 1등인 사람의 서류심사 등수를 firstLimit 으로 지정했다. 이를 이용해서, 조금이라도 시간을 줄이려고 더 작은 한계점을 갖고 있는 쪽을 기준으로 반복문을 돌려서 답을 얻었다.

성공한 전체 코드는 아래와 같다.

import java.io.*;
import java.util.*;

public class sample {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine());
        for(int i = 0 ; i < T; i++){
            int N = Integer.parseInt(br.readLine());
            HashMap<Integer, Integer> hashMapFirst = new HashMap<Integer, Integer>();
            HashMap<Integer, Integer> hashMapSecond = new HashMap<Integer, Integer>();
            int firstLimit = 0;
            int secondLimit = 0;
            for(int j = 0; j < N; j++){
                String line = br.readLine();
                int first = Integer.parseInt(line.split(" ")[0]);
                int second = Integer.parseInt(line.split(" ")[1]);
                if (first == 1) secondLimit = second;
                if (second == 1) firstLimit = first;
                hashMapFirst.put(first, second);
                hashMapSecond.put(second, first);
            }
            int cnt = 1;
            if(firstLimit < secondLimit){
                for(int j = 2; j <= firstLimit; j++){
                    if(hashMapFirst.get(j) < secondLimit) {
                        secondLimit = hashMapFirst.get(j);
                        cnt++;
                    }
                }
            } else {
                for(int j = 2; j <= secondLimit; j++){
                    if(hashMapSecond.get(j) < firstLimit){
                        firstLimit = hashMapSecond.get(j);
                        cnt++;
                    }
                }
            }
            bw.write(cnt + "\n");
        }

        bw.flush();
        br.close();
        bw.close();
    }
}

성공하고 나서, 한가지 맘에 안 들었던게, 시간이 1500ms로 상당히 오래 걸린 점이다. 약간 손을 봐줄 필요성이 있다.

 

1946번: 신입 사원

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