글 읽기 - [Java] BST를 직접 구현해야할까요?

a41798175 1년 전 0

현재 가방의 최대 무게를 list로 저장해서 get(int index)와 remove(int index)에서 시간이 너무 오래 걸립니다. (10%에서 시간초과)

C++이라면 multiset을 쓰는게 제일 좋아보이는데(중복 + lower bound), 직접 BST를 구현하는게 속이 편할까요?

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

public class Main {

	static StringBuilder sb = new StringBuilder();
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

	static int T;
	static int n;
	static int m;

	static Jewerly[] jew;
	static int[] bag;
	static ArrayList<Integer> list = new ArrayList<>();

	static String str;
	static String[] spl;

	static long sum = 0;

	public static void main(String[] args) throws IOException {
		str = br.readLine();
		spl = str.split(" ");
		n = Integer.parseInt(spl[0]);
		m = Integer.parseInt(spl[1]);
		jew = new Jewerly[n];
		bag = new int[m];

		for (int i = 0; i < n; i++) {
			str = br.readLine();
			spl = str.split(" ");
			jew[i] = new Jewerly(Integer.parseInt(spl[0]), Integer.parseInt(spl[1]));
		}

		Arrays.sort(jew, Collections.reverseOrder());

		for (int i = 0; i < m; i++) {
			str = br.readLine();
			bag[i] = Integer.parseInt(str);
		}
		
		Arrays.sort(bag);
		list = new ArrayList<>();
		
		for (int i = 0; i < m; i++) {
			list.add(bag[i]);
		}

		for (int i = 0; i < n; i++) {
			if (list.isEmpty()) {
				break;
			}
			int lb = lowerBound(jew[i].weight);
			if (lb != list.size()) {
				sum += jew[i].value;
				list.remove(lb);
			}
		}
		System.out.println(sum);
	}
	
	public static int lowerBound(int tgt) {
		int start = 0;
		int end = list.size();
		int half;
		while (end - start > 0) {
			half = (start + end) / 2;
			if (list.get(half) < tgt) {
				start = half + 1;
			} else {
				end = half;
			}
		}
		return end;
	}
}

class Jewerly implements Comparable<Jewerly> {
	int weight;
	int value;

	Jewerly(int w, int v) {
		weight = w;
		value = v;
	}

	@Override
	public int compareTo(Jewerly o) {
		if (value == o.value) {
			if (weight < o.weight) {
				return -1;
			} else if (weight == o.weight) {
				return 0;
			} else {
				return 1;
			}
		} else if (value < o.value) {
			return -1;
		} else {
			return 1;
		}
	}
}

list에서 remove하는 건 한 번당 O(n)이라 당연히 시간 초과고요, priority queue로 풀이 가능합니다. 그냥 BST를 쓰는 건 극단적 케이스 때문에 시간 초과 날 것 같고요, BBST로 풀고 싶다면 제가 옛날에 AVL tree를 구현해서 플래 3 문제를 풀어야 할 일이 있었는데(그 문제는 심지어 더 쉬운 풀이가 정해였음) 코드가 360줄이 나왔습니다. 그러니 무슨 ICPC world final 준비라도 하는 게 아니면 굳이 BBST를 구현해야 할까...? 싶은 생각이 듭니다.

a41798175 1년 전 0

답변 감사합니다.

bamgoesn 1년 전 0

자바에 트리맵 트리셋 있지 않나요?

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

문제

문제

출처

ICPC

[Java] BST를 직접 구현해야할까요?

a41798175 1년 전 0

invrtd_h 1년 전 1

a41798175 1년 전 0

bamgoesn 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말