sorting & thinking 7번 최소 회의실 개수

자바 코딩테스트 - it 대기업 유제

7. "최소 회의실 개수" 문제 해법

해결된 질문

작성

237

안녕하세요 강사님 자바 알고리즘 입문 강좌에 이어 이번 강좌 까지 들으며 많은 도움을 받고 있는 수강생입니다. 우선 양질의 강의를 제공해주신 것에 감사드립니다.

이번 문제에서 저는 아래와 같이 코드를 작성했습니다. 자료구조 파트 마지막 문제와 유사하다고 생각했서 아래와 같이 풀었습니다.

저는 해법 영상에서와 같은 논리라고 생각하는데 혹시 논리적 오류가 있을까요?

public int solution(int[][] meetings) {
    int answer = 0;
    PriorityQueue<Meeting> pq = new PriorityQueue<>();
    Arrays.sort(meetings, (a, b) -> a[0] - b[0]);

    for (int[] meeting : meetings) {
        if (pq.isEmpty()) {
            pq.add(new Meeting(meeting[1], answer));
            answer++;
        } else {
            if (pq.peek().end <= meeting[0]) {
                pq.add(new Meeting(meeting[1], pq.poll().room));
            } else {
                pq.add(new Meeting(meeting[1], answer));
                answer++;
            }
        }
    }

    return answer;
}

java 코딩-테스트

답변 2

김태원

지식공유자

안녕하세요^^

Meeting 클래스까지 있는 풀코드를 올려주세요. 에지케이스가 있는지 확인해볼께요.

lano

질문자

풀코드는 아래와 같습니다!

class Meeting implements Comparable<Meeting> {
    int end;
    int room;

    public Meeting(int end, int room) {
        this.end = end;
        this.room = room;
    }

    @Override
    public int compareTo(Meeting o) {
        return this.end - o.end;
    }
}

class Solution {
    public int solution(int[][] meetings) {
        int answer = 0;
        PriorityQueue<Meeting> pq = new PriorityQueue<>();
        Arrays.sort(meetings, (a, b) -> a[0] - b[0]);

        for (int[] meeting : meetings) {
            if (pq.isEmpty()) {
                pq.add(new Meeting(meeting[1], answer));
                answer++;
            } else {
                if (pq.peek().end <= meeting[0]) {
                    pq.add(new Meeting(meeting[1], pq.poll().room));
                } else {
                    pq.add(new Meeting(meeting[1], answer));
                    answer++;
                }
            }
        }

        return answer;
    }

    public static void main(String[] args) {
        Solution T = new Solution();
        System.out.println(T.solution(new int[][]{{0, 10}, {20, 25}, {5, 15}, {2, 5}}));
        System.out.println(T.solution(new int[][]{{1, 30}, {2, 15}, {3, 10}, {4, 12}, {6, 10}}));
        System.out.println(T.solution(new int[][]{{3, 9}, {1, 10}, {5, 8}, {10, 15}, {9, 14}, {12, 14}, {15, 20}}));
        System.out.println(T.solution(new int[][]{{0, 5}, {2, 7}, {4, 5}, {7, 10}, {9, 12}}));
    }
}

김태원

지식공유자

네. 풀코드를 보고 테스트도 해봤는데 논리적 오류가 없어 보입니다. 좋은 코드입니다.

인프런 AI 인턴

안녕하세요, 인프런 AI 인턴입니다.

귀하의 코드에서는 알고리즘이 올바르게 작동합니다. 또한 자료구조 파트 마지막 문제와 유사하다면, 동일한 알고리즘을 사용하는 것이 적절해 보입니다. 따라서 논리적인 오류는 발견되지 않았습니다.

하지만, 코드를 더 개선해 볼 수도 있습니다. 예를 들어, 위 코드에서는 answer 변수를 높이는 곳을 놓칠 수 있습니다. 이 경우, 답이 올바르게 계산되지 않습니다. 또한, 불필요한 연산을 줄일 수 있다면 성능을 더 개선할 수 있을 것입니다.

즉, 아래와 같은 코드를 추천합니다.

public int solution(int[][] meetings) {
int answer = 0;
PriorityQueue pq = new PriorityQueue<>();
Arrays.sort(meetings, (a, b) -> a[0] - b[0]);

for (int[] meeting : meetings) {
    if (pq.isEmpty()) {
        pq.add(new Meeting(meeting[1], answer));
    } else {
        if (pq.peek().end <= meeting[0]) {
            pq.poll();
        } else {
            answer++;
        }
        pq.add(new Meeting(meeting[1], answer));
    }
}

return ++answer;

}

기존의 코드에서, 만약 pq.isEmpty()인 경우, answer 변수를 1 증가시키고 pq에 추가하는 것이 좋습니다. 그리고, pq.poll()를 할 때 answer 변수를 갱신하는 것도 잊지 마세요. 마지막으로, ++answer를 반환하여 답을 계산하면 됩니다.

이 방법을 적용하면, 성능이 더 향상될 것입니다. 이번 문제 풀이에 대한 질문을 보내주셔서 감사합니다.

인프런 커뮤니티 질문&답변

sorting & thinking 7번 최소 회의실 개수