[javaScript] Softeer - [21년 재직자 대회 예선] 좌석 관리

 

https://softeer.ai/class/devcrew/study/resource/detail/description/6267?id=155&resourceId=84

Softeer - 현대자동차그룹 SW인재확보플랫폼

 

현대자동차그룹에서 사내 식당 매니저로 일하는 기항이는 점심 시간에 맞춰 일을 하고 있다. 오늘 일은 사람들이 사회적 거리두기를 잘 지키면서 식당 좌석에 앉도록 상황을 관리하는 일이다.

 

현재 식당에는 좌석 N×M개가 N행 M열로 나열되어 있는데, 각 좌석에는 (1,1)에서 (N,M)로 좌표가 배정되어 있다. x행 y열에 있는 좌석의 좌표는 (x,y)이다.

 

점심 시간에는 많은 사람들이 식당을 드나든다. 사번이 id인 어떤 사원이 식당에 왔다면, 다음 조건에 맞춰 이 사원을 위한 좌석을 배정해준다.

 

현재 K개의 좌석이 차 있고, 이 중 i번째 좌석은 (xi,yi)라고 하자. 이 상황에서 어떤 좌석 (X,Y)의 안전도 DX, Y는 

이다.

즉, 다른 사람까지의 거리 중 가장 가까운 거리다. 단, 방역 수칙에 따르면 사람들은 상하좌우에 바로 붙어 앉을 수 없다.

 

 

또한 아래의 그림에서 처럼 경계 밖은(좌, 하) 고려하지 않는다.

 

 

기항이는 현재 비어있는 좌석 (X,Y) 중에서 방역 수칙을 고려하는 동시에, 안전도가 가장 높은 좌석을 새로 들어오는 사람에게 배정해준다.

배정해줄수 있는 좌석 중 안전도가 가장 높은 좌석이 여럿 있을 수 있다. 이 때는 그 중에서 X가 가장 낮은 좌석을, X도 같다면 Y가 가장 낮은 좌석을 배정해 준다. 특수하게, 현재 모든 좌석이 비어있다면 (1,1)이 배정된다.

 

사번이 id인 어떤 사원이 식당에서 떠난다면, 그 사원이 있던 자리는 빈 자리가 된다. 각 사원들에게 주어지는 점심 식사는 단 한번이므로, 여러 번 점심을 먹을 수는 없다. 그러므로 이미 점심을 먹은 사원은 돌려보내야 한다.

 

이외에도 각 직원의 점심 식사 여부에 따른 처리가 요구되는데, 출력 형식을 참고하여 모든 작업을 적절히 처리해보자.

 

제약조건

1 ≤ N, M ≤ 20

1 ≤ Q ≤ 3×104

1 ≤ id ≤ 104

입력형식

첫 번째 줄에 세 자연수 N, M, Q가 주어진다.

다음 Q개의 줄에는 각 줄마다 처리해야 하는 작업이 In {id} 혹은 Out {id}의 형태로 주어진다.

출력형식

Q개의 줄에 걸쳐서, i번째 줄에는 i번째 작업을 처리한 결과를 출력한다.

각 작업마다 출력하는 방식은 다음과 같다.

 

작업이 In {id}로 주어졌을 때

- 사번이 id인 사원이 현재 좌석에 앉아 밥을 먹고 있다면, {id} already seated.를 출력한다.

- 사번이 id인 사원이 이미 밥을 먹고 떠났다면, {id} already ate lunch.를 출력한다.

- 사번이 id인 사원이 자리가 가득 차서 좌석을 배정받는 데 실패했다면, There are no more seats.를 출력한다.

- 사번이 id인 사원이 성공적으로 좌석 (x,y)에 앉았다면, {id} gets the seat ({x}, {y}).를 출력한다.

 

작업이 Out {id}로 주어졌을 때

- 사번이 id인 사원이 아직 점심을 먹지 못했다면, {id} didn't eat lunch.를 출력한다.

- 사번이 id인 사원이 이미 밥을 먹고 좌석을 떠났다면, {id} already left seat.를 출력한다.

- 사번이 id인 사원이 좌석 (x,y)에 앉아 있었다면, {id} leaves from the seat ({x}, {y}).를 출력한다. 이 사원은 점심을 먹은 상태로 기록된다.

입력예제1

1 3 10 Out 1 In 1 In 2 In 2 In 3 Out 2 In 3 Out 2 Out 1 In 1

출력예제1

1 didn't eat lunch. 1 gets the seat (1, 1). 2 gets the seat (1, 3). 2 already seated. There are no more seats. 2 leaves from the seat (1, 3). 3 gets the seat (1, 3). 2 already left seat. 1 leaves from the seat (1, 1). 1 already ate lunch.

입력예제2

4 4 7 In 7 In 6 In 5 In 4 In 3 In 2 In 1

출력예제2

7 gets the seat (1, 1). 6 gets the seat (4, 4). 5 gets the seat (1, 4). 4 gets the seat (4, 1). 3 gets the seat (2, 2). 2 gets the seat (3, 3). There are no more seats.

 

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
})

let N, M, Q;
let count = 0;
let seatTable = 0;
rl.on('line', function(x){
    if(count == 0){
        [N,M,Q] = x.split(' ').map(Number);
        seatTable = Array.from(Array(N+1), () => Array(M+1).fill(null));
        // console.log(`N: ${N}, M: ${M}, Q: ${Q}`);
    }else{
        let OutIn = x.split(' ')[0];
        let id = x.split(' ')[1];
        mainFunc(OutIn, id);
        if(count == Q){
            rl.close();
        }
    }
    count++;
    
}).on('close', function(){})

//거리 계산
function calculateDistance(x, y, x2, y2) {
    return Math.sqrt(Math.pow(x - x2, 2) + Math.pow(y - y2, 2));
}

let idList = {};//id:{seat: Free/{x:X, y:Y}}
// 자리 찾기
function findSeat(id) {
    let maxDistance = -1;
    let chosenSeat = {};

    for (let i = 1; i <= N; i++) {
        for (let j = 1; j <= M; j++) {
            let seat = seatTable[i][j];

            if (seat === null && isSafe(i, j)) {                            
                let minDistance = Infinity;
                for (let existingId in idList) {
                    let existingSeat = idList[existingId]['seat'];
                    if (existingSeat !== "Free") {
                        let distance = calculateDistance(i, j, existingSeat['x'], existingSeat['y']);
                        minDistance = Math.min(minDistance, distance);
                    }
                }
                
                if (minDistance > maxDistance) {
                    maxDistance = minDistance;
                    chosenSeat = { x: i, y: j };
                }
            }
        }
    }

    return chosenSeat;
}

// 안전한지 확인
function isSafe(x, y) {
    // Check above, below, left, right for existing employees
    if (
        (x > 1 && seatTable[x - 1][y] !== null) ||
        (x < N && seatTable[x + 1][y] !== null) ||
        (y > 1 && seatTable[x][y - 1] !== null) ||
        (y < M && seatTable[x][y + 1] !== null)
    ) {
        return false;
    }

    return true;
}


function mainFunc(OutIn, id){
    if(OutIn == 'In'){
        if(idList[id] != undefined){
            if(idList[id]['seat'] == "Free"){
                console.log(id+" already ate lunch.")
            }else {
                console.log(id+" already seated.")
            }            
        }else{
            // 자리 찾기
            let chosenSeat = findSeat(id);
            if (Object.keys(chosenSeat).length === 0) {
                // 실패
                console.log("There are no more seats.");
            } else {
                // 성공
                let x = chosenSeat['x'];
                let y = chosenSeat['y'];
                seatTable[x][y] = id;
                idList[id] = { seat: { x, y } };
                console.log(id + " gets the seat (" + x + ", " + y + ").");
            }
        }
        
    }else{
        if(idList[id] == undefined){
            console.log(id+" didn't eat lunch.")
        }else{
            if(idList[id]['seat'] == "Free"){
                console.log(id+" already left seat.")
            }else {
                let x = idList[id]['seat']['x'];
                let y = idList[id]['seat']['y'];
                seatTable[x][y] = null;
                idList[id]['seat'] = "Free";                
                console.log(id+" leaves from the seat (" + x + ", " + y + ").")
            }
        }
    }
    
}