-
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
우선순위큐 이해부족인지 버그인지...
20.11.17 19:17 작성 조회수 279
1
안녕하세요 선생님. 정말 기본 문법으로 질문 드리기는 싫었는데 맞게 이해한것 같은데도 잘 이해가 안되는 현상이 있어서 글 쓰러 왔습니다=_=
MeetingRoom2가 잘 안풀려서 해설을 보고 우선순위큐를 먼저 사용해보려고 했고 Interval클래스의 start변수가 작은게 먼저 나오도록 우선순위를 주어서 실행해 봤지만 아래와 같은 결과가 나왔습니다.
제 생각으로는 minhip부분에서
start : 0, end : 30
start : 5, end : 10
start : 15, end : 20
순서로 나와야 하고 제가 잘못 이해한건가 싶어서 다른 코드는 안건드리고 인풋을 몇개 추가해보면
예상대로 나오는 상황입니다.
제가 뭔가 이해를 잘못하고 있는걸까요?
문제가 되는 코드는 아래와 같습니다. 감사합니다~
public class PriorityQueueExample {
class Interval{
Integer start;
Integer end;
public Interval() {
}
public Interval(Integer start, Integer end) {
this.start = start;
this.end = end;
}
public void print(){
System.out.println("start : " + start + ", end : " + end);
}
}
public int solution(int[][] input) {
List<Interval> fixedInput = new ArrayList<>();
for (int[] row : input) {
Interval interval = new Interval(row[0], row[1]);
fixedInput.add(interval);
}
fixedInput.sort((o1, o2) -> o1.end - o2.end );
System.out.println("sortedInput");
for (Interval interval : fixedInput) {
interval.print();
}
Queue<Interval> minHeap = new PriorityQueue<>(fixedInput.size(), (o1, o2) -> o1.start - o2.start);
for (Interval interval : fixedInput) {
minHeap.add(interval);
}
System.out.println("minhip");
for (Interval interval : minHeap) {
interval.print();
}
return 0;
}
public static void main(String[] args) {
MeetingRoom2 proposal = new MeetingRoom2();
int input[][] = {{0,30},{5,10},{15,20}};//이상한 예제1
// int input[][] = {{0,30},{5,10},{35,20}};//이상한 예제2
// int input[][] = {{0,30},{5,10},{15,20},{4, 60}};//정상 예제3
// int input[][] = {{0,30},{5,10},{35,20},{4, 60}};//정상 예제4
proposal.solution(input);
}
}
인프런 질문 편집기에 코드 올리는 기능이 있길래 써봤는데 회색으로 잘 안보이게 표시되서 똑같은코드 사진으로도 붙여두겠습니다
답변을 작성해보세요.
0
푸샵맨 코딩스터디
지식공유자2020.11.23
안녕하세요.
답변을 늦게드리게 되어 정말 죄송합니다.
먼저 질문주신 meetingRoom2 문제는 정말 중요한 문제입니다.
객체 sorting, priorityQueue 사용하는거 꼭 나오는 스타일이죠
일단 주신 예제를 돌려봤는데요.
이부분을 고치시면 됩니다.
fixedInput.sort((o1, o2) -> o1.end - o2.end);
=> fixedInput.sort((o1, o2) -> o1.start - o2.start);
코딩셤 보실때 문제를 정확히 이해하셔야합니다.
대충 이해했다가 한참 코딩했는데 , 아 이게 아니구나 그런 순간 시간 다 날려먹으니까요
meetingRoom2 문제는
회의실을 예약하는데 예를들어
1시5분-1시10분,
1시15분-1시20분,
1시0분-1시30분
이런게 랜덤하게 있으니까 이걸 먼저 start타임으로 소팅을 합니다.
그러면 시작시간이 0분, 5분, 15분이 나오겠죠
그 다음에 우선순위큐를 사용합니다. 우선순위는 start타임으로 잡으면 순서대로 되죠
결론은 우선순위를 사용하기 위해서 미리 소팅을 해준다고 보시면됩니다.
감사합니다.
답변 1