[프로그래머스] 입국심사 - 자바(Java)

문제 링크

프로그래머스

문제 설명

n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 

처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.

모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.

입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution을 작성해주세요.

제한사항

• 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다.
• 각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다.
• 심사관은 1명 이상 100,000명 이하입니다.

입출력 예

n	times	return
6	[7, 10]	28

---

문제 풀이

[고려사항]

입국심사를 기다리는 사람(n)의 최대값이 1,000,000,000(십억)이고, 시간복잡도 O(n)으로 풀어야한다.

[알고리즘, 구현방법]

times에 담긴 각 심사관의 심사 시간이 더 짧은 순으로 배정을 해서 n명을 입국심사한다.

어떤 시점에서 심사 시간이 더 긴 심사관이 비어있는 상태라해도 더 짧게 끝낼 수 있는 심사관이 심사해야 최솟값을 구할 수 있다.

 

X 1차 생각

times를 값이 작은 순서대로 정렬해서, 더 짧게 끝낼 수 있는 심사관이 우선 심사할 수 있게 한다.

맨 처음에는 별도의 조건 없이 times 배열 길이 = 심사관 수만큼 사람을 배정한다.

총 심사 소요시간 변수(answer)에는 입국심사하는 사람의 심사 시간을 누적한다.

 

그런데 이렇게 순차적으로 심사관을 배정하면 고려해야하는 조건이 많아진다.

ex) 입출력 예시에서 나왔듯 20분이 지난 시점에서 10분이 걸리는 심사관이 비어있지만, 1분 더 기다려서 7분이 걸리는 심사관이 심사해야 최소 시간이 나오는 예시

 

✅ 2차 생각

프로그래머스에 이분탐색으로 분류되어있는 것에서 힌트를 얻어서

심사 소요시간에 대한 이분탐색으로 계산해야겠다고 생각했다.

• 이분탐색은 오름차순 또는 내림차순으로 정렬된 배열에 적용 가능한 탐색 기법으로, 정렬된 배열에서 특정 값을 찾을 때 정중앙에 위치한 값을 활용하면 아주 빠른 속도로 탐색을 끝낼 수 있는 방법이다.

탐색 기준을 시간의 범위로 잡아서 이분탐색을 수행한다.

기준이 되는 mid값을 소요시간으로 두고, 그 시간(mid분)에 몇 명을 심사할 수 있는지 계산한다.

계산 값이 심사 받아야하는 인원(n)과 같다면 반환한다.

 

예를들어, mid = 30이고 심사시간이 각각 7분, 10분 걸리는 심사관이 있다면,

30/7 + 30/10 = 4+3 = 7명이 30분안에 심사를 받을 수 있다는 뜻이다.

 

여기서 28분, 29분을 같은 예시로 계산하면 모두 6명이 나오는데, 

이는 심사 받아야하는 인원(n)이 나오더라도 그보다 더 적은 시간내에 심사를 할 수도 있음을 의미한다.

 

따라서 반환하는 조건을 심사 받아야 하는 인원(n) == 계산한 값 으로 하면 안된다.

최소 심사 시간을 구해야하기 때문에, 이분탐색시 양 끝값인 left, right를 left > right로 조건을 두어야 

n명이 모두 심사를 받은 시간이라해도 더 적은 시간을 찾을 수 있다.

[풀이 과정]

1. 심사 소요시간이 짧은 순으로 배열 정렬
   
   • times에 담긴 각 심사관의 심사 시간이 더 짧은 순으로 배정하기 위함
2. 최대 소요시간 계산
   • 가장 긴 심사시간 * 심사 받아야하는 총 인원
3. 이분탐색 하면서 최소 시간 구하기
   • left = 0분 , right = 최대 소요시간 , mid = (left + right) / 2
   • n명이 모두 심사가능한 시간이라해도 그보다 더 최솟값이 있을 수 있으므로,
     • 반복문 탈출 조건을 심사 받아야 하는 인원(n) == 계산한 값으로 하지 않음
     • 반복문 탈출 조건은 left > right 로 설정 (while문의 수행 조건으로는 left <= right가 됨)
   • mid분에 계산한 심사 가능 인원이 n보다 작다면,
     • 해당 시간안에 모든 사람을 심사할 수 없다는 뜻이므로, mid보다 큰 값의 범위를 탐색
   • mid분에 계산한 심사 가능 인원이 n보다 크거나 같다면, 
     • mid보다 작은 값의 범위를 탐색
     • 현재 값보다 최솟값이 있을 수 있으므로 우선 answer에 저장 후 진행
4. left <= right 가 FALSE가 되면 반복문 탈출해서 answer 반환

[Java 문법]

int[] to List

1차 생각을 구현하기 위해 int 배열을 List로 변환하는 방법에 대해 찾아보다가 알게된 내용을 포스팅 했다.

[Java] Array를 List로 변환 : int[] to List<Integer>

 

1차 시도 실패

이분탐색에 필요한 right 값, 

즉 최대 소요시간 계산시 우항인 n, times[times.length-1]을 long 타입으로 변환하지 않아서 실패했다.

long right = n * times[times.length-1];

🔼 실패코드 원인 부분

 

int * int = int인데, int 값의 범위를 넘어서면서(=오버플로우 발생) long 변수에 할당하여 문제가 발생한 것이다.

n의 최대값은 1,000,000,000(십억)이고 심사관은 최대 100,000(10만)명이라서 

두 수의 최대값은 1,000,000,000 * 100,000 = 100,000,000,000,000(100조)라는 어마무시하게 큰 수가 나온다. 

 

int형은 할당되는 메모리의 크기가 4바이트로, 최대값은 2의 31승 - 1인 2,147,483,647이므로 당연히 오버플로우가 발생한다.

long형은 할당되는 메모리의 크기가 8바이트로, 최대값은 2의 63승 - 1인 9,223,372,036,854,775,807라서 범위가 넘지 않는다.

 

* 2의 n승보고 대략적인 0의 개수 확인하기

2의 31승으로 계산을 해보면, 2의 10승 = 1,024 ≒ 10의 3승

2의 31승 ≒ (2의 10승)의 3승 ≒ (10의 3승)의 3승 = 10의 9승

2의 63승 ≒ (2의 10승)의 6승 ≒ (10의 3승)의 6승 = 10의 18승

 

따라서 int형은 오버플로우 발생 가능성이 있으므로, 우항 변수를 long 타입으로 변환하여 계산하는 것으로 바꿨다.

 

정답 코드

public static long solution(int n, int[] times) {
    Arrays.sort(times); // 심사 소요시간이 짧은 순으로 정렬
    long answer = 0; // 최소 심사 시간(최종 결과)

    long left = 0;
    // 최대 소요시간 = 가장 긴 심사시간 * 심사 받아야하는 총 인원
    long right = (long)n * (long)times[times.length-1]; // int형 오버플로우 발생 가능성이 있으므로, 우항 변수를 long 타입으로 변환하여 계산
    // n명이 모두 심사가능한 시간이라해도, 그보다 더 최솟값이 있을 수 있으므로, while조건을 (n == complete)로 하지 않음
    while (left <= right) {
        long mid = (left + right) / 2;
        long complete = 0; // mid 분안에 심사를 할 수 있는 인원수
        // mid 분 안에 심사를 할 수 있는 인원수 계산
        for (int i=0; i < times.length; i++) {
            complete += mid / times[i]; // 각 심사 시간으로 나눠서 심사 가능 인원 계산
        }

        // 심사 가능 인원이 n보다 작다면, 해당 시간안에 모든 사람을 심사할 수 없다는 뜻이므로, mid보다 큰 값의 범위를 탐색
        if (complete < n) {
            left = mid + 1;
        } else { // 계산한 심사한 사람 수가 n보다 크거나 같다면
            right = mid - 1; // mid보다 작은 값의 범위를 탐색
            answer = mid; // 현재 값보다 최솟값이 있을 수 있으므로 우선 answer에 저장 후 진행
        }
    }
    return answer;
}

 

 

참고 포스팅

[ 알고리즘 ] 이분탐색(Binary Search), upper_bound, lower_bound (C++)

JAVA 기본 자료형 & 데이터 타입 - 한눈에 정리