아직 계정이 없으신가요? 회원가입

Dev. Talk

강의실 배정 performance 한개 코드는 정답 다른 하나는 오답(java)

회원사진m100409
280 views2021-10-19 21:07

정답 코드


import java.util.*;
import java.io.*;


public class Main
{	
	static class Data {
		int start;
		int end;

		public Data(int start, int end) {
			this.start = start;
			this.end = end;
		}
	}

public static void main(String[] args) throws NumberFormatException, IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	
		int num = Integer.parseInt(br.readLine());
		ArrayList<Data> list = new ArrayList<>();
		for (int i = 0; i < num; i++) {
			String[] ary = br.readLine().split(" ");
			Data data = new Data(Integer.parseInt(ary[0]), Integer.parseInt(ary[1]));
			list.add(data);
		}
		br.close();
		if(list.size() == 0){
			System.out.println(0);
			return;
		}else if(list.size() == 1){
			System.out.println(1);
			return;
		}
			
		Collections.sort(list, new Comparator<Data>() {
			public int compare(Data arg0, Data arg1) {
				int r = Integer.compare(arg0.start, arg1.start);
				if (r == 0) {
					r = Integer.compare(arg0.end, arg1.end);
				}
				return r;
			};
		});
		
		Data prevData = list.get(0);
		int count = 1;
		for(int i = 1; i < list.size(); i++){
			if(prevData.end <= list.get(i).start){
				prevData = list.get(i);
				count++;
			}else if(prevData.end > list.get(i).end){
				prevData = list.get(i);
			}
		}
	
		
		System.out.println(count);
	}

}



시간초과 나는 코드


import java.util.*;
import java.io.*;


public class Main
{		public static void main(String[] args) throws IOException {
	//	Scanner sc = new Scanner(System.in);
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int num = Integer.parseInt(br.readLine());
		PriorityQueue<Integer> startList = new PriorityQueue<>();
		HashMap<Integer, Integer> map = new HashMap<>();
		for (int i = 0; i < num; i++) {
			String[] ary = br.readLine().split(" ");
			int start = Integer.parseInt(ary[0]);
			int end =  Integer.parseInt(ary[1]);
			if (!startList.contains(start)){
				startList.offer(start);
				map.put(start, end);
			} else {
				if (map.get(start) > end) {
					map.put(start, end);
				}
			}
		}
		br.close();
		if (startList.size() == 0) {
			System.out.println(0);
			return;
		} else if (startList.size() == 1) {
			System.out.println(1);
			return;
		}

		int prevEnd = map.get(startList.poll());
		int count = 1;
		while (!startList.isEmpty()) {
			int start = startList.poll();
			int end = map.get(start);
			if (prevEnd <= start) {
				prevEnd = end;
				count++;
			} else if (prevEnd > end) {
				prevEnd = end;
			}
		}

		System.out.println(count);
	}
}




시간초과나는 코드가 더 효율성 좋다고 판단하여 짠 코드인데 왜 시간초과가 날까요?

인풋을 받으면서 priority queue에 넣어 정렬이 필요없고 그때 그때 강의 끝나는 시간을 비교하여 최소값으로 업데이트합니다.

인풋 받은 후 sort할 필요가 없는데 왜  time out 에러가 나는지 조언 부탁드립니다.


답을 구해놓고도 좀 찝찝합니다.