-
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
회의실 만남(구현부분)과 현관문 출입순서(자료구조) 질문드립니다.
23.07.16 11:37 작성 조회수 335
0
회의실 만남은 구현으로 풀고 현관문 출입순서는 큐로 풀었는데, 회의실 만남은 큐로 못 푸나요??
다른 차이가 있을까요???
답변을 작성해보세요.
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
김태원
지식공유자2023.07.17
안녕하세요^^
현관문 출입순서는 각 사람의 현관문 도착시간이 정확하게 입력으로 주어지는 반면에 회의실 만남은 각 사람의 입실시간과 퇴실시간이 정확이 주어지지 않습니다. 회의실 만남은 최대한 서로 만나지 않게 각 사람의 입실과 퇴실의 시간을 찾는게 관건인 문제입니다. 회의실 만남을 큐로 해결하는 것은 저는 해법이 떠오르지 않네요. 불가능할 것 같은데 혹시 회의실 만남을 큐로 도전해보시고 성공하시면 코드를 공유하면 좋겠습니다.
답변 2