글 읽기 - 제 로직의 어디가 틀렸는지 모르겠습니다.. 반례라도 있다면 부탁드립니다.

augustine91 4년 전 0

요는 현재 수업 중인 리스트를 통해서

만약 현재 수업 중인 리스트의 첫 번째 요소의 T보다 큰 새로운 S가 들어온 경우,

현재 수업 중인 리스트의 크기를 최대값과 비교하여 저장하고,

현재 수업 중인 리스트의 요소돌의 T와 새로 들어온 요소 S를 비교하여 T <= S 인 경우를 모두 제거하고,

새로운 요소를 다시 수업 중인 리스트에 넣는 것입니다.

반례와 잘못된 로직을 알려주시면 감사합니다.

package p11000;

import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {

	static int N;
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scan = new Scanner(System.in);
		PriorityQueue<Pair> pq = new PriorityQueue<Pair>();
		ArrayList<Pair> list = new ArrayList<>();
		ArrayList<Pair> deleteList = new ArrayList<>();
		
		N = scan.nextInt();
		
		int s, e;
		for(int i=0; i<N; i++) {
			s = scan.nextInt();
			e = scan.nextInt();
			
			pq.add(new Pair(s,e));
		}
		
		Pair p, p2, p3;
		int result = 0;
		while(!pq.isEmpty()) {
			p = pq.poll(); // 우선순위 큐에서 값을 꺼내옴
			
			if(list.size() > 0) {
				p2 = list.get(0); // 현재 진행중인 수업 중 가장 빠른 시간의 요소를 꺼내옴
				// System.out.println(p2.s + " , " + p2.e);
				
				if(p.s >= p2.e) { // 만약 현재 수업중인 것보다 뒤에 시작하는 수업이라면
					if(result < list.size()) // 현재 수업 중인 수의 최대값을 비교
						result = list.size();
					
					deleteList.clear();
					for(int i=0; i<list.size(); i++) { // 현재 수업 중인 요소 중에
						p3 = list.get(i);
						if(p.s >= p3.e) { // 새로운 수업의 시작 시간보다 작거나 같은 끝나는 시간을 가진 요소를
							// System.out.println("p.s : " + p.s + " p.e : " + p.e + " / p3.s : " + p3.s + " p3.e : " + p3.e);
							deleteList.add(p3); // 지우기 위한 리스트에 추가
						}
					}
					
					for(int i=0; i<deleteList.size(); i++) { // 해당 요소를 현재 수업 중인 리스트에서 제거
						// System.out.println("p.s : " + p.s + " p.e : " + p.e + " / p3.s : " + deleteList.get(i).s + " p3.e : " + deleteList.get(i).e);
						list.remove(deleteList.get(i));
					}
				} 
				
				list.add(new Pair(p.s, p.e)); // 리스트에 새로이 추가
			} else {
				list.add(new Pair(p.s, p.e));
			}
		}
		
		if(result < list.size())
			result = list.size();
		
		System.out.println(result);
	}

}

class Pair implements Comparable<Pair> {
	int s, e;
	
	Pair(int s, int e){
		this.s = s;
		this.e = e;
	}
	
	@Override
	public int compareTo(Pair o) {
		// TODO Auto-generated method stub
		if(this.s < o.s) return -1; // 시작시간이 앞서는 게 우선
		else if(this.s == o.s && this.e < o.e) return -1; // 시작시간이 동일하다면, 끝나는 시간이 앞서는 게 우선
		return 1;
	}
}

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

문제

문제

출처

ICPC

제 로직의 어디가 틀렸는지 모르겠습니다.. 반례라도 있다면 부탁드립니다.

augustine91 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말