문제
https://softeer.ai/practice/6267
Softeer - 현대자동차그룹 SW인재확보플랫폼
현대자동차그룹에서 사내 식당 매니저로 일하는 기항이는 점심 시간에 맞춰 일을 하고 있다. 오늘 일은 사람들이 사회적 거리두기를 잘 지키면서 식당 좌석에 앉도록 상황을 관리하는 일이다.
softeer.ai
해설
이 문제에 대한 코드는 딱 3가지만 잘 유념해서 적으면 문제 없이 정답이라는 결과를 얻을 수 있다.
1. 점심을 먹었는가, 안먹었는가, 또는 먹고 있는가에 대한 로직.
2. 위험도를 계산하는 로직.
3. 그리고 가장 가까운 거리를 계산하는 로직.
이 세가지만 문제없이 작성한다면 빈틈 없이 깔끔한 코드를 완성할 수 있다.
1. 점심을 먹었는가, 안먹었는가, 또는 먹고 있는가에 대한 로직.
1번 로직을 완성하기 위해서는 우선 각각의 id의 점심 식사 여부 또는 먹고 있는 중을 나타낼 수 있는 데이터 구조가 필요하다.
id_table = [0 for _ in range(10001)] # 한번도 안먹었으면 0, 먹었으면 1, 먹고 있으면 위치 [x,y]를 저장할 것이다.
이 데이터 구조는 위처럼 표현할 수 있다. 이 문제에서 사원의 id는 최대 10000까지 주어진다고 말했다. 그렇기에 1을 더해 10001 만큼의 공간을 만들어주고, 각각의 사원의 id의 식사여부는 이 table에 담을 것이다. 만약 아직 안먹었다면 0을, 이미 먹었다면 1을, 그리고 먹는 중이라면 위치 [x,y]를 담아주는 방식으로 사용할 것이다.
for _ in range(Q):
# "In"/"Out" 과 아이디를 담는다.
inout, p_id = sys.stdin.readline().split()
p_id = int(p_id)
if inout == "In":
# 아직 점심을 안먹었을 때
if id_table[p_id] == 0:
# 자리를 배정해주는 함수 ( Return True (배정성공) or False(배정실패) )
if givePosition(p_id, id_table, env):
# 배정 결과를 출력한다.
print(f"{p_id} gets the seat ({id_table[p_id][1]}, {id_table[p_id][0]}).")
else:
print("There are no more seats.")
# 점심을 이미 먹고 떠났을 때
elif id_table[p_id] == 1:
print(f"{p_id} already ate lunch.")
# 점심을 먹고 있을 때 (id_table[p_id] = [x,y])
else:
print(f"{p_id} already seated.")
else: # inout == "Out"
# 아직 점심을 안먹었을 때
if id_table[p_id] == 0:
print(f"{p_id} didn't eat lunch.")
# 점심을 이미 먹고 떠났을 때
elif id_table[p_id] == 1:
print(f"{p_id} already left seat.")
# 현재 먹고 있는 경우
else:
# 떠났음을 출력하고,
print(f"{p_id} leaves from the seat ({id_table[p_id][1]}, {id_table[p_id][0]}).")
# 자리 비움으로 바꾸고
env[id_table[p_id][1]][id_table[p_id][0]] = 0
# 이미 먹었음으로 갱신한다.
id_table[p_id] = 1
그리고는 데이터를 받아들임과 동시에 "In"과 "Out"에 따라, 그리고 밥을 아직 먹지 않았는가, 이미 먹었는가, 그리고 먹고 있는 중인가에 따른 각각의 로직을 이 문제에 맞게 작성한다.
마지막으로 이 부분에 있어서 사원을 가장 안전한 자리에 넣는 작업을 구현하는 것이 가장 중요하다. 이는 givePosition 이라는 함수를 만들고, 안전한 자리에 넣는 걸 성공했다면 "True"를, 실패했다면 "False"를 출력하도록 만든다. 그리고 이 결과에 따라서도 문제에서 나온 요구사항대로 출력문을 작성할 수 있다.
2. 위험도를 계산하는 로직.
위험도를 계산하는 로직은 각각의 자리를 기준으로 (1) 사회적 거리두기를 위해 현재 위치를 비롯하여 상하좌우에 누가 앉아있는지를 판단하고, (2) 각각의 위치에서 식사를 하고 있는 다른 사원과 가장 가까운 거리를 계산하고, (3) 그 가장 가까운 거리가 가장 큰 위치 [x,y]에 사원을 넣어줌과 동시에 환경 env에도 1로 표시해준 후, (4) 자리 배치에 성공했을 시 "True"를, 실패했을 시 "False"를 구현하도록 하는 코드를 작성하면 된다.
# 좌석 환경을 구현한다.
env = [[0 for _ in range(M+2)] for _ in range(N+2)]
# 안전도가 가장 높은 위치를 id_table에 저장해주는 함수
def givePosition(p_id, id_table, env):
max_safety = 0
for y in range(1, N+1):
for x in range(1, M+1):
# 그 자리가 비어있고, 상하좌우 모두 아무도 앉아있지 않을 때
if (env[y][x] == 0) and (env[y-1][x] == 0) and (env[y+1][x] == 0) and (env[y][x-1] == 0) and (env[y][x+1] == 0):
# 최소 거리를 구하고,
min_dist = nearest_dist(x, y, env)
# 만약 지금 위치에서 최소 거리가 현재 최대 안전도보다 클 때
if (min_dist > max_safety):
# 최대 안전도를 갱신해주고 그 위치를 넣어준다.
max_safety = min_dist
id_table[p_id] = [x, y]
# 자리가 배정되었는지 아닌지 확인한다.
if max_safety == 0:
return False
else:
env[id_table[p_id][1]][id_table[p_id][0]] = 1
return True
코드를 작성하면 위와 같이 깔끔하게 표현할 수 있다.
3. 그리고 가장 가까운 거리를 계산하는 로직.
마지막으로 주변에서 밥먹고 있는 사람들과 거리를 계산했을 때, 가장 가깝게 근접한 거리를 구하는 코드를 작성해야 하는데, 이는 각각의 x, y 위치를 하나하나 확인하고, 그 자리에 누군가가 앉아있을 경우 그 사람과의 거리를 계산하고, 그렇게 모두 계산한 후 가장 작은 값을 출력하면 된다.
def nearest_dist(x, y, env):
# N과 M이 20 이하이므로 넉넉잡아 1000으로 최소값을 설정해준다.
min_dist = 1000
# 환경 내의 모든 위치를 하나하나 돌아다니며 거리를 계산한다.
for loc_y in range(1, N+1):
for loc_x in range(1, M+1):
# 만약 해당 자리에 누군가가 앉아있을 경우
if env[loc_y][loc_x] == 1:
dist = (x-loc_x)**2 + (y-loc_y)**2
# 그리고 최소값을 min_dist에 저장한다.
if dist < min_dist:
min_dist = dist
return min_dist
그 코드는 위와 같이 표현할 수 있다.
코드
import sys
# 자연수 N, M, Q를 받아들인다.
N, M, Q = map(int, sys.stdin.readline().split())
# 좌석 환경을 구현한다.
env = [[0 for _ in range(M+2)] for _ in range(N+2)]
# 각각의 id에 대한 정보를 저장한다. (id는 10^4 보다 작거나 같으므로 공간을 10001개 준비한다.)
id_table = [0 for _ in range(10001)] # 한번도 안먹었으면 0, 먹었으면 1, 먹고 있으면 위치 [x,y]를 저장할 것이다.
def nearest_dist(x, y, env):
# N과 M이 20 이하이므로 넉넉잡아 1000으로 최소값을 설정해준다.
min_dist = 1000
# 환경 내의 모든 위치를 하나하나 돌아다니며 거리를 계산한다.
for loc_y in range(1, N+1):
for loc_x in range(1, M+1):
# 만약 해당 자리에 누군가가 앉아있을 경우
if env[loc_y][loc_x] == 1:
dist = (x-loc_x)**2 + (y-loc_y)**2
# 그리고 최소값을 min_dist에 저장한다.
if dist < min_dist:
min_dist = dist
return min_dist
# 안전도가 가장 높은 위치를 id_table에 저장해주는 함수
def givePosition(p_id, id_table, env):
max_safety = 0
for y in range(1, N+1):
for x in range(1, M+1):
# 그 자리가 비어있고, 상하좌우 모두 아무도 앉아있지 않을 때
if (env[y][x] == 0) and (env[y-1][x] == 0) and (env[y+1][x] == 0) and (env[y][x-1] == 0) and (env[y][x+1] == 0):
# 최소 거리를 구하고,
min_dist = nearest_dist(x, y, env)
# 만약 지금 위치에서 최소 거리가 현재 최대 안전도보다 클 때
if (min_dist > max_safety):
# 최대 안전도를 갱신해주고 그 위치를 넣어준다.
max_safety = min_dist
id_table[p_id] = [x, y]
# 자리가 배정되었는지 아닌지 확인한다.
if max_safety == 0:
return False
else:
env[id_table[p_id][1]][id_table[p_id][0]] = 1
return True
for _ in range(Q):
# "In"/"Out" 과 아이디를 담는다.
inout, p_id = sys.stdin.readline().split()
p_id = int(p_id)
if inout == "In":
# 아직 점심을 안먹었을 때
if id_table[p_id] == 0:
# 자리를 배정해주는 함수 ( Return True (배정성공) or False(배정실패) )
if givePosition(p_id, id_table, env):
# 배정 결과를 출력한다.
print(f"{p_id} gets the seat ({id_table[p_id][1]}, {id_table[p_id][0]}).")
else:
print("There are no more seats.")
# 점심을 이미 먹고 떠났을 때
elif id_table[p_id] == 1:
print(f"{p_id} already ate lunch.")
# 점심을 먹고 있을 때 (id_table[p_id] = [x,y])
else:
print(f"{p_id} already seated.")
else: # inout == "Out"
# 아직 점심을 안먹었을 때
if id_table[p_id] == 0:
print(f"{p_id} didn't eat lunch.")
# 점심을 이미 먹고 떠났을 때
elif id_table[p_id] == 1:
print(f"{p_id} already left seat.")
# 현재 먹고 있는 경우
else:
# 떠났음을 출력하고,
print(f"{p_id} leaves from the seat ({id_table[p_id][1]}, {id_table[p_id][0]}).")
# 자리 비움으로 바꾸고
env[id_table[p_id][1]][id_table[p_id][0]] = 0
# 이미 먹었음으로 갱신한다.
id_table[p_id] = 1
결과
'알고리즘 > 소프티어' 카테고리의 다른 글
| [파이썬] Softeer 연습문제 #27. [HSAT 2회 정기 코딩 인증평가 기출] 사물인식 최소 면적 산출 프로그램 완벽해설 (0) | 2024.01.18 |
|---|---|
| [파이썬] Softeer 연습문제 #26. [21년 재직자 대회 예선] 이미지 프로세싱 완벽해설 (1) | 2024.01.16 |
| [파이썬] Softeer 연습문제 #24. [21년 재직자 대회 예선] 회의실 예약 완벽해설 (0) | 2024.01.12 |
| [파이썬] Softeer 연습문제 #23. [21년 재직자 대회 예선] 전광판 완벽해설 (1) | 2024.01.11 |
| [파이썬] Softeer 연습문제 #22. [21년 재직자 대회 예선] 비밀 메뉴 완벽해설 (1) | 2024.01.10 |
