• 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    미해결

회의실 만남(구현부분)과 현관문 출입순서(자료구조) 질문드립니다.

23.07.16 11:37 작성 조회수 335

0

회의실 만남은 구현으로 풀고 현관문 출입순서는 큐로 풀었는데, 회의실 만남은 큐로 못 푸나요??

다른 차이가 있을까요???

답변 2

·

답변을 작성해보세요.

1

나의서재님의 프로필

나의서재

2023.07.19

public int[] solution(int[] enter, int[] exit){
    int totalWorker = enter.length;
    int[] answer = new int[totalWorker];

    // 나갈사람들
    Deque<Integer> exitWorkers = new LinkedList<>();
    for (int exitWorker : exit) {
        exitWorkers.offer(exitWorker);
    }

    // 만난 사람들을 검증하는 배열
    boolean[][] hasMeet = new boolean[totalWorker + 1][totalWorker + 1];
    for (int self = 0; self <= totalWorker; self++) {
        // 자기 자신과는 만날 수 없다.
        hasMeet[self][self] = true;
    }

    // 회의실에 있는 사람들
    Set<Integer> workersInMeetingRoom = new HashSet<>();
    while (!exitWorkers.isEmpty()) {
        for (int enterWorker : enter) {
            workersInMeetingRoom.add(enterWorker);

            for (int workerInMeetingRoom : workersInMeetingRoom) {
                if (!hasMeet[workerInMeetingRoom][enterWorker]) {
                    answer[enterWorker - 1]++;
                    answer[workerInMeetingRoom - 1]++;
                    hasMeet[workerInMeetingRoom][enterWorker] = true;
                    hasMeet[enterWorker][workerInMeetingRoom] = true;
                }
            }

            while (workersInMeetingRoom.contains(exitWorkers.peek())) {
                int exitWorker = exitWorkers.poll();
                workersInMeetingRoom.remove(exitWorker);
            }
        }
    }

    return answer;
}


저는 Set과 Queue(Deque)을 이용해서 풀어봤습니다. 컴파일 시 출력은 일치하지만 좋은 코드인지는 잘 모르겠습니다!

0

안녕하세요^^

현관문 출입순서는 각 사람의 현관문 도착시간이 정확하게 입력으로 주어지는 반면에 회의실 만남은 각 사람의 입실시간과 퇴실시간이 정확이 주어지지 않습니다. 회의실 만남은 최대한 서로 만나지 않게 각 사람의 입실과 퇴실의 시간을 찾는게 관건인 문제입니다. 회의실 만남을 큐로 해결하는 것은 저는 해법이 떠오르지 않네요. 불가능할 것 같은데 혹시 회의실 만남을 큐로 도전해보시고 성공하시면 코드를 공유하면 좋겠습니다.