[Java, Python]_1092_배

hanseungjune·2023년 7월 22일
0

알고리즘

목록 보기
32/33
post-thumbnail

작성 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class ship_1092 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        ArrayList<Integer> cranes = new ArrayList<>();
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++){
            cranes.add(Integer.parseInt(st.nextToken()));
        }

        int m = Integer.parseInt(br.readLine());

        ArrayList<Integer> boxes = new ArrayList<>();
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < m; i++) {
            boxes.add(Integer.parseInt(st.nextToken()));
        }

        if (Collections.max(cranes) < Collections.max(boxes)) {
            System.out.println(-1);
            return;
        }

        int[] position = new int[n];
        for (int i = 0; i < n; i++){
            position[i] = 0;
        }

        boolean[] checked = new boolean[m];
        for (int i = 0; i < m; i++) {
            checked[i] = false;
        }

        Collections.sort(cranes);
        Collections.reverse(cranes);

        Collections.sort(boxes);
        Collections.reverse(boxes);

        int result = 0;
        int count = 0;

        while (true) {
            if ( count == boxes.size() ) {
                break;
            }
            for (int i = 0; i < n; i++) {
                while (position[i] < boxes.size()) {
                    if ( !checked[position[i]] && cranes.get(i) >= boxes.get(position[i]) ) {
                        checked[position[i]] = true;
                        position[i]++;
                        count++;
                        break;
                    }
                    position[i]++;
                }
            }
            result++;
        }
        System.out.println(result);
    }
}

로직

이 코드는 배의 크레인들로 박스를 옮기는 문제를 해결하는 자바 알고리즘입니다. 이 알고리즘은 박스들을 가장 효율적으로 옮기기 위해 크레인들의 용량을 최대한 활용하는 것을 목표로 합니다.

코드는 먼저 크레인들의 수(n)와 각 크레인의 최대 용량(cranes)을 입력받습니다.

그 다음, 옮겨야 하는 박스들의 수(m)와 각 박스의 무게(boxes)를 입력받습니다.

만약 가장 무거운 박스의 무게가 가장 높은 용량을 가진 크레인의 용량보다 크다면, -1을 출력하고 프로그램을 종료합니다. 이는 그 박스를 옮길 수 있는 크레인이 없다는 것을 의미합니다.

각 크레인이 현재 어떤 박스를 확인하는지를 추적하기 위해 position 배열을 만들고 0으로 초기화합니다.

어떤 박스가 이미 옮겨졌는지를 확인하기 위해 checked 배열을 만들고 모두 false로 초기화합니다.

cranes와 boxes 리스트를 내림차순으로 정렬합니다. 이렇게 하면 용량이 큰 크레인과 무거운 박스부터 비교할 수 있습니다.

모든 박스를 옮길 때까지 다음 단계를 반복합니다:

각 크레인에 대해, 크레인이 현재 확인하는 박스(position[i])가 아직 옮겨지지 않았고(!checked[position[i]]), 그 크레인이 그 박스를 옮길 수 있다면(cranes.get(i) >= boxes.get(position[i])), 박스를 옮기고 (checked[position[i]] = true;), 크레인이 다음 박스를 확인하게 합니다(position[i]++). 이때, 옮겨진 박스의 수(count)도 증가시킵니다.

만약 크레인이 현재 확인하는 박스를 옮길 수 없다면, 크레인은 다음 박스를 확인합니다(position[i]++).

모든 크레인이 한 번씩 박스를 확인한 후에는 시간을 증가시킵니다(result++).

모든 박스를 옮긴 후, 그때까지 걸린 시간(result)을 출력합니다.

이 알고리즘은 각 시간 단위에서 각 크레인이 옮길 수 있는 가장 무거운 박스를 옮기므로, 박스들을 옮기는 데 필요한 최소 시간을 계산합니다.

파이썬

import sys
from collections import deque
input = sys.stdin.readline

n = int(input())
cranes = list(map(int, input().split()))
m = int(input())
boxes = list(map(int, input().split()))

if max(cranes) < max(boxes):
    print(-1)
    sys.exit()

positions = [0] * n
checked = [False] * m

cranes.sort(reverse=True)
boxes.sort(reverse=True)

result = 0
count = 0

while True:
    if count == len(boxes):
        break
    for i in range(n):
        while positions[i] < len(boxes):
            if not checked[positions[i]] and cranes[i] >= boxes[positions[i]]:
                checked[positions[i]] = True
                positions[i] += 1
                count += 1
                break
            positions[i] += 1
    result += 1

print(result)
profile
필요하다면 공부하는 개발자, 한승준

1개의 댓글

comment-user-thumbnail
2023년 7월 22일

공감하며 읽었습니다. 좋은 글 감사드립니다.

답글 달기