백준 1092, 배 - Greedy
https://www.acmicpc.net/problem/1092
1. 아이디어
- 각 크레인의 최대 무게 리스트, 각 박스의 무게 리스트를 큰 순으로 정렬
- 가장 큰 무게의 박스, 가장 큰 무게의 크레인부터 확인
1) 해당 박스를 해당 크레인으로 옮길 수 있는 경우
- 해당 박스를 박스 리스트에서 삭제
- 다음 박스, 다음 크레인 확인
2) 해당 박스를 해당 크레인으로 옮길 수 없는 경우
- 다음 박스(현재 해당 박스 이하의 무게)를 현재 크레인으로 옮길 수 있는지 확인
=> 모든 크레인을 확인한 경우, 경과 시간 +1
2. 자료구조
ArrayList<Integer>
2개: 각 크레인의 최대 무게 리스트, 각 박스의 무게 리스트
3. 시간 복잡도
- 크레인 최대 무게 리스트 정렬: 50 log_2 50 ~= 250
- 박스 무게 리스트 정렬: 10^4 log_2 10^4 ~= 12 x 10^4
코드
import java.io.*;
import java.util.*;
public class Main {
static int n; // 크레인 개수
static List<Integer> craneWeights = new ArrayList<>(); // 각 크레인의 최대 무게
static int m; // 박스 개수
static List<Integer> boxWeights = new ArrayList<>(); // 각 박스의 무게
static int minTime; // 출력, 최소 시간
static void solution() {
// 박스를 모두 옮길 수 없는 경우
if (boxWeights.get(0) > craneWeights.get(0)) {
minTime = -1;
return;
}
while (!boxWeights.isEmpty()) {
int boxIdx = 0;
for (int i = 0; i < craneWeights.size(); ) { // 주의) for 문에 i++ 없음
if (boxIdx == boxWeights.size()) // 마지막 박스까지 확인한 경우
break; // => 남은 첫 번째 박스, 첫 번째 크레인부터 다시 확인
if (boxWeights.get(boxIdx) <= craneWeights.get(i)) {
boxWeights.remove(boxIdx); // 해당 박스 옮김(제거)
i++; // 다음 크레인
}
else // [i] 크레인으로 박스 못 옮기는 경우
boxIdx++; // => [i] 크레인으로 다음 박스 옮길 수 있는지 확인
}
minTime++;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(
new InputStreamReader(System.in)
);
StringTokenizer st;
n = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++)
craneWeights.add(Integer.parseInt(st.nextToken()));
m = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine());
for (int i = 0; i < m; i++)
boxWeights.add(Integer.parseInt(st.nextToken()));
// 2개 리스트를 각각 무게 큰 순으로 정렬
// Collections.sort(craneWeights, (w1, w2) -> w2 - w1);
Collections.sort(craneWeights, Collections.reverseOrder());
Collections.sort(boxWeights, Collections.reverseOrder());
solution();
System.out.println(minTime);
}
}
Author And Source
이 문제에 관하여(백준 1092, 배 - Greedy), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@silver_star/백준-1092-배-Greedy저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)