글 읽기 - 시간초과가 걸리는 이유!!

dydwo0740 1년 전 0

이분탐색 lowerbound를 통해 가방을 찾고 가방이 존재한다면 그 가방을 삭제해줌으로써 시간을 줄였는데 안되는 이유가 있을까요??

package hello;

import java.awt.List;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

class Jewelry {
	long price;
	int weight;

	Jewelry(int weight, long price) {
		this.weight = weight;
		this.price = price;
	}
}

public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		ArrayList<Jewelry> list = new ArrayList<>();
		ArrayList<Integer> bag = new ArrayList<>();

		int N = Integer.parseInt(st.nextToken());

		int K = Integer.parseInt(st.nextToken());
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			int weight = Integer.parseInt(st.nextToken());
			long price = Long.parseLong(st.nextToken());
			list.add(new Jewelry(weight, price));
		}

		for (int i = 0; i < K; i++) {
			st = new StringTokenizer(br.readLine());
			int max = Integer.parseInt(st.nextToken());
			bag.add(max);
		}

		bag.sort(Comparator.naturalOrder());// 이분탐색을 위한 오름차순 정렬

		Comparator<Jewelry> nc = new Comparator<Jewelry>() {

			@Override
			public int compare(Jewelry o1, Jewelry o2) {
				// TODO Auto-generated method stub
				if (o1.price == o2.price) {
					return o1.weight - o2.weight;
				}
				return (int)o2.price - (int)o1.price;
			}
		};

		Collections.sort(list, nc);
		
		long sum = 0;
		
		for (int i = 0; i < N; i++) {
			int weight = list.get(i).weight;
			long price = list.get(i).price;
			
			int start = 0;
			int end = bag.size();
			
			while (start < end) {
				int mid = (start + end) / 2;
				if (bag.get(mid) < weight) {
					start = mid + 1;
				} else {
					end = mid;
				}
			}//이분탐색
			
			if (start != bag.size()) {
				sum += price;
				bag.remove(start);
			} // 가방을 찾음

			if (bag.isEmpty()) {
				break;
			}
		}

		bw.write(sum + "\n");
		bw.flush();

	}

	public static void getSubsequence(int idx, int end, int sum, ArrayList<Integer> list, ArrayList<Integer> ans) {
		if (idx == end) {
			ans.add(sum);
			return;
		}
		getSubsequence(idx + 1, end, sum + list.get(idx), list, ans);
		getSubsequence(idx + 1, end, sum, list, ans);
	}

}

spahb0563 1년 전 0

Arraylist는 중간에 값을 삭제하면 뒤에있는 모든 값들을 한칸씩 앞으로 이동시켜야 하는데 list 크기가 크면 어떻게 될까요 ?

dydwo0740 1년 전 0

앗 그렇네요 ㅠㅠㅠ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간초과가 걸리는 이유!!

dydwo0740 1년 전 0

spahb0563 1년 전 0

dydwo0740 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말