상어 초등학교 (골드 5)
긴 구현 문제이다. 최근 대기업 코테 트렌드 문제이기도 하다. 문제에서 주어진 조건과 1,2,3을 잘 따라가서 코딩하면 된다.
순서대로 들어오는 학생 id로 하여금 빈 자리에 한하여 해당 빈 자리마다 인접한 곳에 좋아하는 학생이 있는지 모두 체크한다. (행위치, 열위치, 인접한 곳에 좋아하는 친구 수 = like), like의 max값이 0이 아닐 경우 max에 해당하는 (행, 열) 데이터만 뽑아 따로 리스트에 append해서 리턴한다.
리턴했을 때 해당 리스트는 세 가지 경우를 가진다.
- max값이 0이고 모든 행열의 like가 0인 경우 (빈 리스트로 처리 되어짐)
- max값에 해당하는 행열요소가 여러개인 경우 (리스트 길이가 2 이상)
- max값에 해당하는 행열요소가 한개인 경우 (리스트 길이가 1)
3인 경우는 처리가 쉽다. 그냥 그 행열에 들어온 학생 id를 추가한다.
1,2인 경우 추가적으로 보아야할 것이 가능성 있는 자리의 주변이 얼마나 비어있는지 추가적으로 확인해야한다.
1의 경우 map에 배치되지 않은 모든 자리를 탐색해야한다. 만약 주변이 얼마나 비었는지 측정했는데 max값이 여러개 겹칠 경우, lowest row, lowest col순으로 최종 배치 위치를 선택한다.
2의 경우 주어진 2개 이상의 행열요소에 대해 주변이 얼마나 비었는지 측정한다. 여기서 또 max값이 중첩된다면 이 또한 lowest row, lowest col순으로 최종 배치 위치를 선택한다.
비슷한 로직이 여러겹 구현되어야 하는 문제이다. 모듈화해서 여러 함수를 만들어 진행하는 것이 틀렸을 때도 금방 고칠 수 있지 않을까 싶다.
from sys import stdin
n = int(stdin.readline())
student_hash = [[] for _ in range(n**2 + 1)]
student_call = []
for i in range(n**2):
student = list(map(int, stdin.readline().split()))
student_idx = student[0]
student_like = student[1:]
student_hash[student_idx] = student_like
student_call.append(student_idx)
class_room = [[0]*n for _ in range(n)]
# 모든 위치에 대해 인접한 칸에 몇 명의 친구가 존재하는지 리턴한다.
def search_like(student_idx, class_room):
length = len(class_room)
like = student_hash[student_idx]
like_student_map = [[0]*length for _ in range(length)]
dxdy = [(0, 1), (0, -1), (1, 0), (-1, 0)]
for i in range(length):
for j in range(length):
if class_room[i][j] == 0:
for k in dxdy:
if 0 <= i + k[0] < length and 0 <= j + k[1] < length:
if class_room[i + k[0]][j + k[1]] in like:
like_student_map[i][j] += 1
# 최댓값들을 가지는 위치를 리스트로 리턴한다.
max_like = max(map(max, like_student_map))
if max_like == 0:
return []
max_like_student = []
for i in range(length):
for j in range(length):
if like_student_map[i][j] == max_like:
max_like_student.append((i, j))
return max_like_student
def optimal_positioner(class_room, max_like_student):
dxdy = [(0, 1), (0, -1), (1, 0), (-1, 0)]
length = len(class_room)
empty_space = [[0]*length for _ in range(length)]
if len(max_like_student) == 0:
for i in range(length):
for j in range(length):
if class_room[i][j] == 0:
for k in dxdy:
if 0 <= i + k[0] < length and 0 <= j + k[1] < length:
if class_room[i + k[0]][j + k[1]] == 0:
empty_space[i][j] += 1
# max
max_empty = max(map(max, empty_space))
max_empty_student = []
for i in range(length):
for j in range(length):
if empty_space[i][j] == max_empty:
max_empty_student.append((i, j))
# sort
max_empty_student.sort(key=lambda x: (x[0], x[1]))
if max_empty == 0:
for i in max_empty_student:
if class_room[i[0]][i[1]] == 0:
return i
return max_empty_student[0]
else:
if len(max_like_student) == 1:
return max_like_student[0]
else:
hash_map_tmp = [0]*len(max_like_student)
for idx, i in enumerate(max_like_student):
# (1,0)
row, col = i
for k in dxdy:
if 0 <= row + k[0] < length and 0 <= col + k[1] < length:
if class_room[row + k[0]][col + k[1]] == 0:
hash_map_tmp[idx] += 1
max_empty = max(hash_map_tmp)
max_empty_student = []
for idx, i in enumerate(max_like_student):
if hash_map_tmp[idx] == max_empty:
max_empty_student.append((i[0], i[1]))
# 정렬
max_empty_student.sort(key=lambda x: (x[0], x[1]))
return max_empty_student[0]
def satisfaction_calculater(class_room):
length = len(class_room)
map_satisfaction = [[0]*length for _ in range(length)]
dxdy = [(0, 1), (0, -1), (1, 0), (-1, 0)]
for i in range(length):
for j in range(length):
like = student_hash[class_room[i][j]]
for k in dxdy:
if 0 <= i + k[0] < length and 0 <= j + k[1] < length:
if class_room[i + k[0]][j + k[1]] in like:
map_satisfaction[i][j] += 1
satisfaction = 0
for i in range(length):
for j in range(length):
like_n = map_satisfaction[i][j]
satisfaction += int(10**(like_n-1))
return satisfaction
for i in student_call:
student_idx = i
max_like_student = search_like(student_idx, class_room)
optimal_position = optimal_positioner(class_room, max_like_student)
class_room[optimal_position[0]][optimal_position[1]] = student_idx
# 만족도 계산
score = satisfaction_calculater(class_room)
print(score)1, 2, 3 더하기 4 (골드 5)
예전에 비슷하게 보았던 dp문제이다. 구하는 것은 전체 경우의 수이다. 바텀 업으로 쌓아가면 된다.
점화식은 dp[i] += dp[i-num] 이며 초기화는 dp[0]를 1로만 해서 1,2,3에 대해
dp[i] += dp[i-1], dp[i] += dp[i-2], dp[i] += dp[i-3]로 반복문을 돌렸다.
from sys import stdin
n = int(stdin.readline())
def count(num):
dp = [0] * (num + 1)
dp[0] = 1
for i in range(1, 4):
for j in range(i, num + 1):
dp[j] += dp[j - i]
return dp[-1]
for i in range(n):
num = int(stdin.readline())
print(count(num))Olympiad Pizza ( Silver 5 )
It is easy to solve this with Queue. participants who need more pizza after receiving it must go back. so i think it is quite so efficient to solve with Queue.
in the first place, we could put all data in our Queue like this (idx, pizza) and then use 'while' repetition with the condition that the queue is empty.
Set the time to 0 initially, and then increment it by 1 inside the while loop. In 'while', you use get() in Queue, if you get pizza == 1, you should record the time at the memory index indicated by 'idx' and else if, put the new data like (idx, pizza - 1)
from sys import stdin
from queue import Queue
n = int(stdin.readline())
par_lst = list(map(int, stdin.readline().split()))
# init #
q = Queue()
for idx, i in enumerate(par_lst):
q.put((idx, i))
time_lst = [0]*n
time = 0
while not q.empty():
idx, pizza_needed = q.get()
time += 1
if pizza_needed == 1:
time_lst[idx] = time
else:
q.put((idx, pizza_needed-1))
for i in range(n):
print(time_lst[i], end=' ')