leetcode - exam room(java)

level - medium
이게 왜..medium..?

[문제 내용]
아..문제 설명하는 것도 힘들다..이건 본문을 가져오는 걸로 대체하겠다..

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(p) have a student sitting in seat 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.

[해결 방법]
아 나는 이게 왜 medium인지...
나만 너무 어려웠나..?
뭔가 한두개씩 조건을 빼먹어서 더 헤맸던것 같다..

본론으로 들어와서,
map을 이용해서 좌석 번호를 key로 하고
value는 다음 좌석과 떨어져있는 길이를 저장하여
가장 멀리 떨어져있는 곳을 찾아서 좌석을 배정하는 방식으로 해결했다.

class ExamRoom {

    int max;
        HashMap<Integer, Integer> seats = new HashMap<>();
        public ExamRoom(int n) {
            max = n-1;
        }

        public int seat() {
            if(seats.size() == 0) {
                seats.put(0, max);
                return 0;
            } else if(seats.size() == 1) {
                for(int key : seats.keySet()) {
                    if(max - key < key) {
                        seats.put(0, key);
                        seats.put(key, max-key);
                        return 0;
                    } else {
                        seats.put(key, max-key);
                        seats.put(max, 0);
                        return max;
                    }
                }
            }

            int len = 0, index = 0, cost = 0;
            boolean multi = false;
            if(!seats.containsKey(0)) {
                ArrayList<Integer> keySet = new ArrayList<>(seats.keySet());
                Collections.sort(keySet);
                len = keySet.get(0);
            }

            for(int key : seats.keySet()) {
                if(len < seats.get(key)/2) {
                    len = seats.get(key)/2;
                    index = key;
                } else if(len == seats.get(key)/2) {
                    if(index > key) {
                        index = key;
                    }
                }
            }

            if(!seats.containsKey(max) && seats.containsKey(max-1)) {
                if(len < 1) {
                    index = max-1;
                }
            }

            int first = index;
            if(!seats.containsKey(first)) {
                seats.put(first, len);
            } else {
                int last = index+seats.get(index);
                if (seats.containsKey(last)) {
                    index = (first + last) / 2;
                    seats.put(index, last - index);
                } else {
                    index = last;
                    seats.put(index, max - index);
                }
                seats.put(first, index-first);
            }

            return index;
        }

        public void leave(int p) {
            for(int key : seats.keySet()) {
                if(key + seats.get(key) == p) {
                    int next = seats.get(p) + p;
                    seats.put(key, next - key);
                    seats.remove(p);
                    return;
                }
            }
            seats.remove(p);
        }
}