99클럽 코테 스터디 3일차 TIL (미들러): [프로그래머스][Java] 11561 징검다리 - level3

 

문제 보기

https://school.programmers.co.kr/learn/courses/30/lessons/43238#

프로그래머스

 

 

풀이

또 이분 탐색!

반복해서 풀어서 그런가 이번엔 더더 쉬웠던 것 같다.

 

1. 최소 시간은 어떻게 구하나?

우선 기다리는 사람이 아니라 심사관에 따라 시간이 다르다는 것을 알아야 한다.

걸리는 시간은 고정적이고 시간 지체 없이 바로 다른 사람을 받을 수 있다는 소리이다.

 

그럼 생각을 달리 해보자.

 

- 기다리는 사람: 6

- 심사관 별 걸리는 시간: 7, 10

- 총 최소 시간: 28

 

반대로 28분 동안 몇 명을 받을 수 있는지를 생각 해보는 건 어떨까?

그러면 간단한 사칙연산 문제로 바뀐다!

 

28/7 = 4

28/10 = 2

총 6명이 된다.

  long sum = 0;
  for (int time : times) {
    sum += mid / time;
    if(sum >= n) {
      break;
    }
  }

 

걸리는 시간을 구하는 이분 탐색을 만들어 보면 되지 않을까?

 

2. 자료형에 주의

최대 1,000,000,000,000,000,000분이 걸릴 수 있는 만큼 자료형에 주의해야 한다.

나는 모든 변수를 long으로 설정했다.

또한 high값을 1,000,000,000,000,000,000으로 설정했다.

 

 

전체 코드

class Solution {
  public long solution(int n, int[] times) {
    long low = 0;
    long high = 1000000000000000000L;

    while (low <= high) {
      long mid = (low + high) / 2;
      long sum = 0;
      for (int time : times) {
        sum += mid / time;
        if(sum >= n) {
          break;
        }
      }
      if(sum < n) {
        low = mid + 1;
      } else {
        high = mid - 1;
      }
    }

    return low;
  }
}

 

 

GitHub 링크

https://github.com/MetroDefro/CodingTest_AutoSave/tree/main/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/3/43238.%E2%80%85%EC%9E%85%EA%B5%AD%EC%8B%AC%EC%82%AC

CodingTest_AutoSave/프로그래머스/3/43238. 입국심사 at main · MetroDefro/CodingTest_AutoSave