Leetcode 855. Exam Room 시험장 착석: 두 가지 해법 제공

Leetcode 855. Exam Room 시험장 착석: 두 가지 해법 제공

855. Exam Room 시험장 착석(두 가지 해법)

제목설명

예:

해답 1

코드 1

해답 2

코드 2

855. Exam Room 시험장 착석(두 가지 해법)

제목 설명

In an exam room, there are N seats in a single row, numbered 0, 1, 2, …, 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. (Also, if no one is in the room, then the student sits at seat number 0.)
Return a class ExamRoom(int N) that exposes two functions: ExamRoom.seat() returning an int representing what seat the student sat in, and ExamRoom.leave(int p) representing that the student in seat number p now leaves the room. It is guaranteed that any calls to ExamRoom.leave§ have a student sitting in seat p.
Note:
1 <= N <= 10^9 ExamRoom.seat() and ExamRoom.leave() will be called at most 10^4 times across all test cases. Calls to ExamRoom.leave§ are guaranteed to have a student currently sitting in seat number p.

예:

Example 1:

Input: ["ExamRoom","seat","seat","seat","seat","leave","seat"], [[10],[],[],[],[],[4],[]]
Output: [null,0,9,4,2,null,5]
Explanation:
ExamRoom(10) -> null
seat() -> 0, no one is in the room, then the student sits at seat number 0.
seat() -> 9, the student sits at the last seat number 9.
seat() -> 4, the student sits at the last seat number 4.
seat() -> 2, the student sits at the last seat number 2.
leave(4) -> null
seat() -> 5, the student sits at the last seat number 5.

​​​​​​​

해답

첫 번째 방법은 하나의vector로 좌석 번호를 저장하고 매번 좌석에 앉을 때마다 그룹을 옮겨다니며 가장 큰 좌석 간격을 찾은 다음에 이 간격의 중간 위치에 앉는다.
좌석을 떠날 때 바이어에서 이 좌석 번호를 삭제하면 됩니다.이 알고리즘의 복잡도는 선형이다.

코드 1

class ExamRoom {
int num = 0;
vector<int > row;
public:
    ExamRoom(int N) {
        num = N;
    }
    
    int seat() {
        if (row.size() == 0) {
        	row.push_back(0);
        	return 0;
        }
        int d = max(row[0], num - 1 - row[row.size() - 1]);
        for (int i = 1;i < row.size(); i ++) {
        	d = max(d, (row[i] - row[i - 1]) / 2);
        }
        if (d == row[0]) {
        	row.insert(row.begin(), 0);
            return 0;
        }
        else {
        	for (int i = 1; i < row.size(); i++) {
        		if ((row[i] - row[i - 1]) / 2 == d) {
        			row.insert(row.begin() + i, (row[i] + row[i - 1]) / 2);
        			return row[i];
        		}
        	}
        }
        row.push_back(num - 1);
        return num - 1;
    }
    
    void leave(int p) {
        for (int i = 0; i < row.size(); i++) {
        	if (row[i] == p)
        		row.erase(row.begin() + i);
        }
    }
};

해답2

두 번째 아이디어 알고리즘의 복잡도는 O(l o g n) O(logn) O(logn)이다. 전역에서 maintain의 set 수조에서 좌석 간격에 따라 큰 것부터 작은 것까지 배열하고 매번 자리에 앉을 때마다 이 set 데이터의 첫 번째 위치의 간격을 빼고 이 간격을 둘로 나누어 이 set 데이터에 삽입한다.
자리를 떠날 때 set 수조에서 자리를 뜨는 사람이 관련된 두 개의 간격을 찾아 이 두 개의 간격을 합친 후에 set에 삽입하면 자리를 뜨는 것이 완성된다.

코드 2

struct IntV
{
	static int N;
	int l, r;
	IntV(int l, int r) : l(l), r(r) {};
	int getDistance() const {
		if (l == 0) return r;
		if (r == N - 1) return N - 1 - l;
		if (r < l) return -1;
		else return (r - l) / 2;		
	} 

	int getInsertPoint() const {
		if (l == 0) return 0;
		if (r == N  - 1) return N - 1;
		else return (l + r) / 2; 
	}
	int operator < (const IntV& a) const {
		int d1 = getDistance();
		int d2 = a.getDistance();
		if(d1 != d2) return d1 > d2;
        	return l < a.l;
	}
};
int IntV :: N = 0;
class ExamRoom{
public:
	set<IntV> interval;
	map<int, int> r2l, l2r;
	ExamRoom(int N) {
		IntV::N = N;
		interval.clear(); l2r.clear(); r2l.clear();
		interval.insert(IntV(0, N - 1));
		l2r[0] = N - 1;
		r2l[N -1] = 0;
	}

	int seat() {
		auto cur = *(interval.begin());
		interval.erase(interval.begin());
		int pos = cur.getInsertPoint();
		cout << pos;
		interval.insert(IntV(cur.l, pos - 1));
		interval.insert(IntV(pos + 1, cur.r));
		l2r[cur.l] = pos - 1;
		r2l[pos - 1] = cur.l;
		l2r[pos + 1] = cur.r;
		r2l[cur.r] = pos + 1;
		return pos;

	}
	void leave(int p) {
		auto r = l2r[p + 1];
		auto l = r2l[p - 1];
		interval.erase(IntV(l, p - 1));
		interval.erase(IntV(p + 1, r));
		interval.insert(IntV(l, r));
		l2r[l] = r;
		r2l[r] = l;
		r2l.erase(p - 1);
		l2r.erase(p + 1);
	}
};