[백준 / BOJ] 1092 배 (Java)

문제

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

1092번: 배

크래인의 갯수 N, 화물박스의 갯수 M이 주어진다.

(1<= N <= 50)

(1 <= M <= 100000)

 

N,M만큼 크래인이 들수있는 무게와, 화물의 무게가 주어진다.

크레인은 매 시간마다 화물을 들수있는데, 이때, 모든 크레인이 한번에 움직인다.

또한 크레인은 자신의 허용무게를 초과하는 화물은 들지못한다.

 

크레인이 모든 화물을 옮기기 까지 걸리는 최소시간을 구하는 문제다.

(만약 옮길수없다면 -1을 출력한다.)

 

풀이

자바를 공부하고있는데, 자바연습겸 풀은 문제다. 

 

"문제를 읽으며 정렬후 이분탐색으로 풀면되겠네" 라고 생각했는데, M과 N의 사이즈가 작아서 완전탐색으로도 풀릴거같길래 완전탐색으로 풀었다.

+ 이분탐색으로 풀려하면 구현이 조금 복잡하다...화물의 무게가 중복값이 있기때문에, 링크드리스트를 이용해 값을 삭제해주며 이분탐색을 돌려야한다. (사실 자바로 처음하는 알고리즘인데, 이걸 구현할 엄두가안났다)

매 쿼리마다 자기가 들수있는 화물의 무게중 가장무거운 화물을 log(M)만에 찾을수있기때문에, 시간복잡도는 O(M)에서 O(logM)으로 줄긴한다.

 

로직은 다음과 같다.

"자신이 들수있는 화물중 가장 무거운 화물을 든다."

 

위 로직을 최대한빠르게 구현하기위해, 정렬후 뒤에서부터 탐색을한다.(이분탐색이 더 빠르긴하다.)

 

시간복잡도를 구해보자.

크레인 하나당 최대 N번 반복하고 크레인은 M개 있으므로, 

MN이다. 이때, 이 과정을 MN번(모든 화물이 없어질때까지)반복하므로 최종 시간복잡도는 O(logMN^2)가 된다. 

이대로는 절대 통과할수없기때문에 여기서 탐색횟수를 줄여줘야한다.

 

로직은 다음과 같다.

"무게 A까지 들수있는 크레인이 어떠한 화물도 들수없다면, 다음번 탐색부터는 해당 크레인의 경우는 제외한다"

 

다시 시간복잡도를 계산해보자.

(위 로직을 추가했을때는 정확한 시간복잡도를 계산하기 까다롭다)

 

1. 모든 N개의 크레인이 제외되는 크레인없이 모두 화물을 집을때,

매 탐색마다 N개씩 줄어들것이므로 총 탐색횟수는 M/N이고, 시간복잡도는 O(NM * M/N)이 된다.

 

2. N개의 크레인이 모두 제외되고 1개의 크레인이 화물을 집을때,

매 탐색마다 1개씩 줄어들고, 제외되는 크레인은 더 이상 봐주지않으므로, 시간복잡도는 O(M^2)이 된다.

 

따라서, 위 알고리즘의 시간복잡도는 테스트케이스에 따라서 O(NM*M/N)과 O(M) 사이이다.

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/1092%20%EB%B0%B0/Main.java

devxb/JJUNalgo