[Softeer]좌석관리 파이썬 풀이
Softeer 좌석관리¶
문제 page: https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=625
일단 문제가 정말 복잡하네요...
복잡한 상황 속에서는 입력과 출력을 어떻게 처리해야하는지 먼저 살펴보면 좋은 것 같습니다.
(하나의 함수 or 클래스를 작성하는 것과 비슷하므로)
좌석관리
'''
inputs:
- N, M, Q
N(int): 식당의 행의 갯수
M(int): 식당의 열의 갯수
Q(int): 작업의 횟수
- In or Out: 사번이 id인 사원이 식당에 들어오는지 or 나가는지
- id number(int): 1 <= id <= 10**4
outputs:
- if In:
1) {id} already seated.
2) {id} already ate lunch.
3) There are no more seats
4) {id} gets the seat ({x}, {y}).
- if Out:
1) {id} didn't eat lunch.
2) {id} already left seat.
3) {id} leaves from the seat({x}, {y}).
'''
문제의 input, output을 살펴보니 문제를 어떻게 접근해야할 지 가닥이 잡히는 듯 합니다.
먼저 input data를 통해 식당의 graph를 만들어야 합니다.
이 때 사원번호는 1부터 시작하므로 비어있는 경우는 0이나 음수로 처리하면 될 것 같습니다.
두번째로 작업이 In인지 Out인지에 따라 알고리즘이 달라집니다.
먼저 In의 경우 수식(안전도 $D_{X, Y}$)을 통해 자리를 지정해줘야 하므로 Out의 경우보다 복잡하네요.
그러므로 Out의 경우를 먼저 생각한 후에 In의 경우를 구현해 봅시다.
Out의 경우는 3가지 입니다.
1) 사원이 점심을 먹지 못했다.
2) 이미 밥을 먹고 좌석을 떠났다.
3) 좌석 (x, y)에 앉아 밥을 먹고 있다.
1) 사원이 점심을 먹지 못했다.
각각의 사원들에 대해 밥을 먹었는지 체크하는 방안을 통해 구현을 할 수 있을 것 같습니다.
이 때 id에 따라 상태를 바로 알 수 있는 자료형이 적합하므로 dict로 구현하는 것이 편할 듯 합니다.
초기화할때는 모두 False로 처리한 후 사원이 좌석에 앉으면 True.
2) 이미 밥을 먹고 좌석을 떠났다.
사원이 밥을 먹었고 좌석에 없는 경우입니다.
밥을 먹었는지는 위에 구현한 방법대로 dict로 확인이 가능합니다.
좌석에 없는지 체크하는 방법은 식당의 각 행을 탐색하면서 해당 사원의 번호가 있는지 체크하면 되겠네요.
3) 좌석 (x, y)에 앉아 밥을 먹고 있다.
식당에 해당 사원의 번호가 있는지 탐색합니다.
다만 우리의 경우 사원이 좌석에 앉자마자 밥을 먹었다고 체크합니다.
즉 해당 사원이 먼저 밥을 먹었는지 체크한 후에 식당에 존재하는지 체크하는 편이 적합해 보입니다.
또한 명령어가 Out이므로 식당[x][y]를 비어있다고 처리합니다.
Out
# num: 사원의 번호
if did_eat[num]: # 2), 3)
if num in 식당:
print('좌석 (x,y)에 앉아 밥을 먹고 있다.')
식당[x][y]=0
else:
print('이미 밥을 먹고 좌석을 떠났다.')
else:
print('사원이 점심을 먹지 못했다.')
In의 경우
1) 현재 좌석에 앉아 밥을 먹고 있다.
2) 이미 밥을 먹고 떠났다.
3) 자리가 가득 차서 좌석을 배정받지 못한다.
4) 성공적으로 좌석 (x, y)에 앉았다.
1) 현재 좌석에 앉아 밥을 먹고 있다.
앞에서 구현한 did_eat[num]을 통해 사원이 밥을 먹었는지(먹고 있는지) 확인할 수 있습니다.
이를 먼저 체크한 후 식당에 해당 사원의 번호가 있다면 1)의 case.
2) 이미 밥을 먹고 떠났다.
did_eat[num] = True 그리고 식당에 사번이 없는 경우.
3) 자리가 가득 차서 좌석을 배정받지 못한다.
4) 성공적으로 좌석 (x,y)에 앉았다.
수식에 겁을 먹고 최후의 최후까지 미룬 알고리즘입니다.
우선 크게, 안전도 $D_{X, Y}$를 계산한 후에 적합한 좌석이 있으면 4), 없으면 3)으로 처리하면 될 것 같습니다.
$$D_{X, Y} = min \sqrt{(x_{i}-X)^2 + (y_{i}-Y)^2} (1<= i <= k)$$
1) 좌석이 비어있는 자리에 대해 알고리즘을 수행한다. if map[row][col]==0
2) $x_{i}$, $y_{i}$는 좌석에 사람이 있는 경우의 행, 열이므로 식당을 탐색하면서 0이 아닌 곳의 index를 구한다.
다만 이 때,
1. [row][col]의 상하좌우에 해당하는 경우는 탐색하지 않는다.
2. 식당 바깥의 경우도 탐색하지 않는다.
3) 수식에 따라 매번 최소값을 갱신해준다.
4) 해당 row, col의 안전도를 저장한다. 안전도[(row, col)] = $D_{X, Y}$
5) 모든 비어있는 자리에 대해 1) ~ 4)의 알고리즘을 수행했다면 max값에 해당하는 행, 열을 구한다.
6) if 거리가 비어있는 경우(상하좌우, 식당 바깥의 경우에 걸려)
print('자리가 가득 차서 좌석을 배정받지 못한다.')
In
# num: 사원의 번호
if did_eat[num]: # 1), 2)
if num in 식당:
print('현재 좌석에 앉아 밥을 먹고 있다')
else:
print('이미 밥을 먹고 떠났다.')
else: # 3), 4)
for row:
for col:
if Map[row][col]==0:
if Map[row-1][col]==0 and ... Map[row][col-1]==0: #상하좌우 비어 있음?
min_dist = math.inf
for i in range(row):
for j in range(col):
if Map[i][j] >0:
now_dist = 안전도
min_dist = min(min_dist, now_dist)
min_dist, (row,col) 저장
if min_dist != None:
Map[row][col] = num
did_eat[num] = True
print('gets the seat (%d, %d)'%(row, col))
else:
print('There are no more seats')
해답¶
from collections import deque
import heapq
import math
N, M, Q = [int(x) for x in input().split()]
Map =[]
Map.append([-1]*(M+2))
for row in range(1, N+1):
Map.append([-1]+[0]*M+[-1])
Map.append([-1]*(M+2))
q = deque()
did_eat = {}
for _ in range(Q):
a, b = [x for x in input().split()]
q.append((a, int(b)))
did_eat[int(b)] = False
is_vacant = {}
while q:
In_Out, num = q.popleft()
if In_Out == 'In':
if did_eat[num]:
is_seated = False
for row in range(1, N+1): # 자리에 있을 때
if num in Map[row]:
print(str(num)+' already seated.')
is_seated = True
break
if not is_seated:
print(str(num) + ' already ate lunch.')
else:
dists=[] # 각각의 자리에 대해 안전도 저장
for row in range(1, N+1):
for col in range(1, M+1):
if Map[row][col] == 0:
if Map[row-1][col] <=0 and Map[row+1][col]<=0 and Map[row][col-1] <= 0 and Map[row][col+1] <= 0:
min_dist = math.inf
for i in range(1, N+1):
for j in range(1, M+1):
if Map[i][j] > 0:
now_dist = math.sqrt((i-row)**2 + (j-col)**2)
min_dist = min(min_dist, now_dist)
heapq.heappush(dists, (-min_dist, row, col))
if not dists==[]: # 적합한 자리가 있을 때
min_dist, row, col=heapq.heappop(dists)
Map[row][col] = num
did_eat[num] = True
print(str(num) +' gets the seat (%d, %d).'% (row, col))
else:
print('There are no more seats.')
else: # In_Out = Out
if did_eat[num]:
is_seated = False
for row in range(1, N+1):
if num in Map[row]: # 사원이 점심을 먹고 자리에 있을 때
is_seated =True
col = Map[row].index(num)
print(str(num) + " leaves from the seat (%d, %d)." % (row, col) )
did_eat[num] = True
Map[row][col] = 0
break
if not is_seated:
print(str(num) + ' already left seat.') #사원이 점심을 먹고 자리에 없을 때
else: # 사원이 점심을 먹지 못했을 때
print(str(num) + " didn't eat lunch.")
1 3 10 Out 1 In 1 In 2 In 2 In 3 Out 2 In 3 Out 2 Out 1 In 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.
