[▲][Softeer][level3][21년 재직자 대회 예선] 좌석 관리 - 파이썬(Python)

https://softeer.ai/practice/info.do?idx=1&eid=625&sw_prbl_sbms_sn=144286 

Softeer

 

Python

5초

1024MB

 

 

문제

 

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

 

현재 식당에는 좌석 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인 어떤 사원이 식당에서 떠난다면, 그 사원이 있던 자리는 빈 자리가 된다. 각 사원들에게 주어지는 점심 식사는 단 한번이므로, 여러 번 점심을 먹을 수는 없다. 그러므로 이미 점심을 먹은 사원은 돌려보내야 한다.

 

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

 

 

입력형식

첫 번째 줄에 세 자연수 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차 : 틀린코드 (23.02.08)

문제가 많은 코드이다 ㅋㅋㅋ 테스트케이스만 맞음

어디가 문제인지는 아니까 다시 고쳐봐야지

import math
import sys
input = sys.stdin.readline 

n, m , q = map(int,input().split())


ALREADY_EAT = 1
NOT_EAT = -1
NOW_EAT = 0

CAN_NOT_SEAT = -2
CAN_SEAT = -1

d = [[1,0],[0,1],[-1,0],[0,-1]]

restaurant = [[CAN_SEAT] * m for _ in range(n)]
check = [NOT_EAT] * 10001 

nowPersonNum = 0
nowEatArea = dict()


def printRestaurant():
    for i in range(n):
        for j in range(m):
            print(restaurant[i][j], end=" ")
        print()


def makeStateAround(r,c, state):

    for i in range(4):
        dr = r + d[i][0]
        dc = c + d[i][1]
        
        if (0<=dr<n) and (0<=dc<m) :
            restaurant[dr][dc] = state


def getSafePercent(r, c): #안전도 구하기
    resultPercent = sys.maxsize

    for nr, nc in nowEatArea.values():
        percent = math.sqrt( (c - nc)**2 + (r - nr )**2 )
        resultPercent = min(resultPercent, percent)

    return resultPercent


def whereIsMySeat():
    
    global nowPersonNum
    
    r,c = 0,0
    safeArea = []
    
    if nowPersonNum <= 0 :
        return 0,0,True

    else:
        #각 영역의 안전도 구하기 #적합한 곳 찾아서 r, c에 할당
        for r in range(n):
            for c in range(m):
                if restaurant[r][c] == CAN_SEAT:
                    safeArea.append([ r,c, getSafePercent(r,c) ])

        if len(safeArea) == 0:
            return -1, -1, False
        else: #안전지역 존재할경우  
            safeArea = sorted(safeArea, key = lambda x : (-x[2],x[0],x[1])) #퍼센트 기준 내림차순 정렬
        
        #safe area 정렬해서 r,c  찾기
        r,c = safeArea[0][0], safeArea[0][1]
        #for r,c,percent in safeArea:
        #    print(f"{r+1}, {c+1} 위치에서 {percent} 입니다 ")
        

        #print()
    
        
        return r, c, True



for _ in range(q):
    inOut, id = map(str, input().split())
    id = int(id)
    
    if inOut == "In":
        if check[id] == NOW_EAT :
            print(f"{id} already seated.")
            continue

        elif check[id] == ALREADY_EAT : 
            print(f"{id} already ate lunch.")
            continue

        r, c, possible  = whereIsMySeat()
    
        if possible: #좌석에 앉음
            print(f"{id} gets the seat ({r+1}, {c+1}).")

            nowPersonNum += 1
            restaurant[r][c] = id
            nowEatArea[id] = [r,c]
            check[id] = NOW_EAT
            makeStateAround(r,c, CAN_NOT_SEAT) #못앉게 만들어야함
            #print(nowEatArea)

            #printRestaurant()


        else: #자리가 가득차서 좌석 배정 실패
            print("There are no more seats.")


    elif inOut == "Out":
        if check[id] == NOT_EAT:
            print(f"{id} didn't eat lunch.")
            continue
            
        elif check[id] == ALREADY_EAT : 
            print(f"{id} already left seat.")
            continue

        elif check[id] == NOW_EAT :
            #내보내줘야함. 
            nowPersonNum -= 1
            r,c = nowEatArea[id]
 
            nowEatArea.pop(id)
            restaurant[r][c] = CAN_SEAT
            makeStateAround(r,c, CAN_SEAT) #앉을 수 있게 만들어야함
            check[id] = ALREADY_EAT



            print(f"{id} leaves from the seat ({r+1}, {c+1}).")

 

 

 

💻  2차 : 정답코드 (23.02.08)

하 일단 로직 자체에 문제가 있음을 파악해서 수정하긴 했는데 얘도 겁나 느리게 채점 됐다

일단 정답이 떴으니 성공적!

 

import math
import sys
input = sys.stdin.readline 

n, m , q = map(int,input().split())


ALREADY_EAT = 1
NOT_EAT = -1
NOW_EAT = 0

CAN_NOT_SEAT = -2
CAN_SEAT = -1

d = [[1,0],[0,1],[-1,0],[0,-1]]

restaurant = [[CAN_SEAT] * m for _ in range(n)]
check = [NOT_EAT] * 10001 

nowPersonNum = 0
nowEatArea = dict()


def printRestaurant():
    for i in range(n):
        for j in range(m):
            print(restaurant[i][j], end=" ")
        print()


def isPossible(r,c):

    for i in range(4):
        dr = r + d[i][0]
        dc = c + d[i][1]
        
        if(0>dr or dr>=n or 0>dc or dc>=m):
            continue

        if restaurant[dr][dc] is not CAN_SEAT:
            return False
   
    return True


def getSafePercent(r, c): #안전도 구하기
    resultPercent = sys.maxsize

    for nr, nc in nowEatArea.values():
        percent = math.sqrt( (c - nc)**2 + (r - nr )**2 )
        resultPercent = min(resultPercent, percent)

    return resultPercent


def whereIsMySeat():
    
    global nowPersonNum
    
    x,y, flag  = 0,0, True
    safeArea = []
    
    if nowPersonNum <= 0 :
        return 0,0,True

    else:
        #각 영역의 안전도 구하기 #적합한 곳 찾아서 r, c에 할당
        for r in range(n):
            for c in range(m):
                if restaurant[r][c] == CAN_SEAT and isPossible(r,c):
                    safeArea.append([ r,c, getSafePercent(r,c) ])
                
        if len(safeArea) == 0:
            x, y, flag = -1, -1, False

        else: #안전지역 존재할경우  
            safeArea = sorted(safeArea, key = lambda x : (-x[2],x[0],x[1])) #퍼센트 기준 내림차순 정렬
            x, y, flag = safeArea[0][0], safeArea[0][1], True
    
        return x, y, flag




for _ in range(q):

    inOut, id = map(str, input().split())
    id = int(id)
    
    if inOut == "In":
        if check[id] == NOW_EAT :
            print(f"{id} already seated.")
            continue

        elif check[id] == ALREADY_EAT : 
            print(f"{id} already ate lunch.")
            continue

        r, c, possible  = whereIsMySeat()
        #print(f"r:{r+1}, c:{c+1}, possible:{possible}")
        if possible: #좌석에 앉음
            
            print(f"{id} gets the seat ({r+1}, {c+1}).")

            nowPersonNum += 1
            restaurant[r][c] = id
            nowEatArea[id] = [r,c]
            check[id] = NOW_EAT
            #printRestaurant()
            
        else: #자리가 가득차서 좌석 배정 실패
            print("There are no more seats.")


    elif inOut == "Out":
        if check[id] == NOT_EAT:
            print(f"{id} didn't eat lunch.")
            continue
            
        elif check[id] == ALREADY_EAT : 
            print(f"{id} already left seat.")
            continue

        elif check[id] == NOW_EAT :
            #내보내줘야함. 
            nowPersonNum -= 1
            r,c = nowEatArea[id]
            nowEatArea.pop(id)
            restaurant[r][c] = CAN_SEAT
            check[id] = ALREADY_EAT

            #printRestaurant()
            print(f"{id} leaves from the seat ({r+1}, {c+1}).")