[Softeer] 좌석 관리(Lv.3) - Day6

📋 개요 

2024.01.30 - [Algorithm/Problem] - [Softeer] GINI야 도와줘(Lv.3) - Day5

2024.01.31 - [Algorithm/Problem] - [Softeer] 택배 마스터 광우(Lv.3) - Day5

[Softeer] 택배 마스터 광우(Lv.3) - Day5

[Softeer] GINI야 도와줘(Lv.3) - Day5

5일차에는 길찾기(bfs), permutaion을 활용해서 풀이를 진행했다. 소프티어 2주챌린지의 6일차이다. 이번에도 어김없이 Lv.3의 문제가 2개 나있다. Lv.3의 문제는 구현도 구현이지만 시간 복잡도 계산을 잘해서 풀이해야 된다는 생각이 많이 든다. 

 

이번에 풀어볼 문제는 Lv.3 좌석관리 이다. (브루트 포스인가.....?)

https://softeer.ai/practice/6267

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
2

🖥️ 내 코드

---

📖  해설 및 느낀점

# 풀이

 

예제2 입력에 관한 gif이다 하나씩 뜯어보면서 코드를 작성해보겠다.

일단 어떤 기능들이 필요한지 명세해보자

• 입력
• 직원 식사 확인 여부
• 안전거리 계산
• 출력

필요한 기능들은 많이 없다. 안전 거리를 계산하는 로직과, 거기서 인원별로 안전거리에 대한 최소 값을 찾은 후 크게는 안전거리가 가장 먼 최대값을 찾아서 빈자리에 사람을 넣으면 된다. 물론 사람이 있다면, 안 넣어도 된다.

 

첫번째 직원 식사 확인 여부를 진행한다. 이건 그리 어렵지 않다. 일단 in/ out으로 분기를 치고 그리고 나서 사용자가 떠난 값을 boolean값으로 저장하여 기존에 먹고 갔다면 true값으로 저장해 들어온 인원이 들어온다면 다른 분기를 태운다. out도 마찬가지이다.

vector<bool> leave(MAX_SIZE, false); // 사용자가 식사를 마쳤는지 여부를 추적하는 배열
map<int, pair<int, int>> user; // 사용자 ID와 그들의 좌표를 매핑하는 사전

if (op == "In") { // 사용자가 들어오는 경우
            if (user.find(user_id) != user.end()) {
                cout << user_id << " already seated.\n";
            } else if (leave[user_id]) {
                cout << user_id << " already ate lunch.\n";
            } else {
                if (assign(user_id, N, M)) {
                    cout << user_id << " gets the seat (" << user[user_id].first << ", " << user[user_id].second << ").\n";
                } else {
                    cout << "There are no more seats.\n";
                }
            }
        } else { // 사용자가 나가는 경우
            if (leave[user_id]) {
                cout << user_id << " already left seat.\n";
            } else if (user.find(user_id) == user.end()) {
                cout << user_id << " didn't eat lunch.\n";
            } else {
                leave[user_id] = true;
                seated[user[user_id].first][user[user_id].second] = false;
                cout << user_id << " leaves from the seat (" << user[user_id].first << ", " << user[user_id].second << ").\n";
                user.erase(user_id);
            }
        }

 

이제 메인 로직인 거리두기 로직을 작성해야하는데 문제를 자세히 살펴보겠다. 우리가 가진 조건은 아래와 같다.

• 상하좌우로 아무도 앉으면 안됨
• 식당이 텅텅 비어있으면 (1,1)자리에 앉히면됨
• 다음번에 들어올 사람이 다른 사람과 가장 먼자리, 즉 안전도가 가장 높은 자리에 앉아야함
• 안전도가 같다면, X랑 Y가 가장 작은 위치에 우선 앉힌다.

여기까지가 조건들이다. 물론, 상하좌우 옆에 벽이 있으면 포함하지 않는다는 한번 생각하라고 꼬아서 낸거 같은데 그냥 내가 생성하는 배열의 크기에 +2를 해주면된다. 그러면 행과 열이 0인 곳과 N+1인 곳 M+1인 곳까지 연산하면서 out of bound 에러를 무시할 수 있다. 배열을 사용한다면 그렇고 vector는 그냥 선언하면 된다. 아래와 같이 쓴다고 생각하면된다

 

그리고 안전도를 구하면서 안전도에 관련된 좌표도 저장해야한다.

void calSafetyLevel(int x , int y){
	for (int i = 1; i < 5; i++)  
    {
        for (int j = 1; j < 5; j++)    
        {
			if(x !=  i && y != j){ //현위치가 아닐때만 안전도에 대해서 연산
				sLayer[i][j] = sqrt(pow (x-i,2 ) + pow (y-j,2)); 
			}
        }
    }
}

 

먼저 안전도를 구하는 공식을 작성해보았다. i=1부터 k까지니깐 반복문안에 작성을 해줘한다. 수학 공식을 사용할때는 cmath해더를 가져와서 사용해야한다.

안전도를 계산하고 거기서 가장 안전도가 작은 cell들중에 가장 큰 cell들에 다음 직원을 앉히면 된다.

 

왜일까?

아래의 그림을 한번 보자.

 

사원 7번이 앉고 나서 가장 안전도가 높은 자리, 즉 가장 먼 자리는 어디일까? (4,4)의 자리이다.

그렇다면, 사원 7번과 6번이 앉고 나서는 어떤 자리가 가장 먼자리 일까?

 

7번 입장에서 보았을때는 (4,2)나 (2,4)가 가장 먼자리 일것이다. 하지만 6번 기준으로 보았을때는 (4,2)나 (2,4)는 가까운 자리이다. 

그렇다면? 7번입장으로 가장 먼거리로 해야할까? 아니다. 최소한의 안전도로 잡고해야 6번 7번 모두가 안전할 수 있는 거리가 나오는거다.

그렇기때문에 직원 입장에서 볼때는 가까운 거리, 안전도가 낮은 것을 기준으로 잡고, 좌석 전체에서 볼때는 안전도가 높은것, 가장 먼 거리 기준으로 좌석에 앉혀야한다.(이해가 갔으면 좋겠는데....)

사실 직관적으로 보았을때는 무조건 (1,4) (4,1)이 멀어보이겠지만 컴퓨터한테 이야기할때는 직관적인게 아니라 왜 그렇게 결과가 도달했는지 알아야한다.(후... 이런점들이 어렵다)

 

브루투포스인거 같기도 하지만 내 개인적인 생각으로는 그냥 구현 문제인거 같다. 일단 Day6를 블로그 포스팅으로 남기고 있지만 따로 해야할 일이 많고 난이도가 어려워지면서 조금 포스팅하는데 시간이 많이 걸린다...! 그래서 일단 7일 50%까지는 포스팅을 진행해보고 차후에 어떻게 해야할지 결정을 해야겠다.

 

C++코드가 이상하더라도 많은 양해 부탁드립니다~