Exam Room[Design,Heap (Priority Queue)Ordered Set]

https://leetcode.com/problems/exam-room/description/

There is an exam room with n seats in a single row labeled from 0 to n - 1.

When a student enters the room, they must sit in the seat that maximizes the distance to the closest person. If there are multiple such seats, they sit in the seat with the lowest number. If no one is in the room, then the student sits at seat number 0.

Design a class that simulates the mentioned exam room.

Implement the ExamRoom class:

• ExamRoom(int n) Initializes the object of the exam room with the number of the seats n.
• int seat() Returns the label of the seat at which the next student will set.
• void leave(int p) Indicates that the student sitting at seat p will leave the room. It is guaranteed that there will be a student sitting at seat p.

 

Example 1:

Input
["ExamRoom", "seat", "seat", "seat", "seat", "leave", "seat"]
[[10], [], [], [], [], [4], []]
Output
[null, 0, 9, 4, 2, null, 5]

Explanation
ExamRoom examRoom = new ExamRoom(10);
examRoom.seat(); // return 0, no one is in the room, then the student sits at seat number 0.
examRoom.seat(); // return 9, the student sits at the last seat number 9.
examRoom.seat(); // return 4, the student sits at the last seat number 4.
examRoom.seat(); // return 2, the student sits at the last seat number 2.
examRoom.leave(4);
examRoom.seat(); // return 5, the student sits at the last seat number 5.

 

Constraints:

• 1 <= n <= 109
• It is guaranteed that there is a student sitting at seat p.
• At most 104 calls will be made to seat and leave.

또 일종의 게임문제다.

얼른 풀어봅시다.

 

-- 한참의 생각 후.. --

 

모르겠다. 도저히 생각이 안 난다.

일종의 자료구조를 만드는 코드라 Python , C , C++ 모든 언어로 

1. Python

class ExamRoom:

    def __init__(self, n: int):
        self.n = n
        self.seated = []

    def seat(self) -> int:
        if not self.seated:
            self.seated.append(0)
            return 0
        else:
            max_dist = self.seated[0]
            pos = 0

            for i in range(len(self.seated)-1) :
                dist = (self.seated[i+1]-self.seated[i])//2
                if dist > max_dist:
                    max_dist = dist
                    pos = self.seated[i]+dist
            if self.n - 1 - self.seated[-1] > max_dist:
                pos = self.n - 1
            
            idx = 0
            while idx < len(self.seated) and self.seated[idx] < pos :
                idx += 1
            self.seated.insert(idx,pos)

            return pos
    def leave(self, p: int) -> None:
        self.seated.remove(p)


# Your ExamRoom object will be instantiated and called as such:
# obj = ExamRoom(n)
# param_1 = obj.seat()
# obj.leave(p)

 

seat 정의하는 놈이 진짜 무지막지하다.

 

보고도 모르겄네 이거;;

 

난이도가 왜 이런가 ㅠㅠ

 

주석 있는 버전은 아래와 같다.

class ExamRoom:
    def __init__(self, n: int):
        self.n = n  # 좌석의 총 개수
        self.seated = []  # 앉아있는 학생들의 위치를 저장하는 리스트

    def seat(self) -> int:
        if not self.seated:  # 아무도 앉아있지 않은 경우
            self.seated.append(0)
            return 0
        
        max_dist = self.seated[0]  # 첫 번째 좌석까지의 거리
        pos = 0
        
        # 인접한 두 학생 사이의 거리를 확인
        for i in range(len(self.seated) - 1):
            dist = (self.seated[i + 1] - self.seated[i]) // 2
            if dist > max_dist:
                max_dist = dist
                pos = self.seated[i] + dist
        
        # 마지막 좌석부터 끝까지의 거리 확인
        if self.n - 1 - self.seated[-1] > max_dist:
            pos = self.n - 1
        
        # 새로운 위치를 정렬된 상태로 삽입
        idx = 0
        while idx < len(self.seated) and self.seated[idx] < pos:
            idx += 1
        self.seated.insert(idx, pos)
        
        return pos

    def leave(self, p: int) -> None:
        self.seated.remove(p)  # p 위치의 학생을 제거

 

 

 

2. C
이건 좀 너무한 거 아니냐고!

#include <stdlib.h>

typedef struct {
    int* seats;     // 앉아있는 학생들의 위치를 저장하는 배열
    int count;      // 현재 앉아있는 학생 수
    int capacity;   // 전체 좌석 수
} ExamRoom;

ExamRoom* examRoomCreate(int n) {
    ExamRoom* room = (ExamRoom*)malloc(sizeof(ExamRoom));
    room->seats = (int*)malloc(sizeof(int) * n);  // 최대 n개의 좌석
    room->count = 0;
    room->capacity = n;
    return room;
}

int examRoomSeat(ExamRoom* obj) {
    if (obj->count == 0) {
        // 아무도 앉아있지 않은 경우, 0번 자리에 배치
        obj->seats[0] = 0;
        obj->count++;
        return 0;
    }

    int maxDist = obj->seats[0];  // 첫 좌석까지의 거리
    int position = 0;             // 선택될 위치

    // 인접한 좌석들 사이의 거리를 확인
    for (int i = 0; i < obj->count - 1; i++) {
        int dist = (obj->seats[i + 1] - obj->seats[i]) / 2;
        if (dist > maxDist) {
            maxDist = dist;
            position = obj->seats[i] + dist;
        }
    }

    // 마지막 좌석부터 끝까지의 거리 확인
    if (obj->capacity - 1 - obj->seats[obj->count - 1] > maxDist) {
        position = obj->capacity - 1;
    }

    // 새로운 위치를 정렬된 상태로 삽입
    int i;
    for (i = obj->count; i > 0 && obj->seats[i - 1] > position; i--) {
        obj->seats[i] = obj->seats[i - 1];
    }
    obj->seats[i] = position;
    obj->count++;

    return position;
}

void examRoomLeave(ExamRoom* obj, int p) {
    // p 위치의 학생을 찾아서 제거
    int i;
    for (i = 0; i < obj->count; i++) {
        if (obj->seats[i] == p) {
            break;
        }
    }
    
    // 찾은 위치부터 나머지 요소들을 한 칸씩 앞으로 이동
    for (; i < obj->count - 1; i++) {
        obj->seats[i] = obj->seats[i + 1];
    }
    obj->count--;
}

void examRoomFree(ExamRoom* obj) {
    free(obj->seats);  // 좌석 배열 메모리 해제
    free(obj);         // ExamRoom 구조체 메모리 해제
}