-
Notifications
You must be signed in to change notification settings - Fork 0
Open
Description
dx = [-1,1,0,0]
dy = [0,0,-1,1]
## 입력
n = int(input())
favo = []
for _ in range(n*n):
line = list(map(int, input().split()))
student, favolist = line[0], line[1:]
favo.append([student, favolist]) ### [4번, [2,5,1,7]]
## 배열 준비
a = [[-1] * n for _ in range(n)]
# for line in a:
# print(line)
# 비어있는 칸 대상으로 탐색
# (인접칸 중 좋아하는 학생의 총 수 up/ 인접칸 중 비어있는 칸의 총 수 up/ 행의 번호 down/ 열의 번호 down)
for number in range(n*n): # len(favo)
#sorts = [[0 * 4] for _ in range(n * n)]
idx = favo[number][0] # 학생 번호
sorts = []
for i in range(n):
for j in range(n):
if a[i][j] == -1:
one = 0
two = 0
for k in range(4):
nx, ny = i+dx[k], j+dy[k]
if 0<=nx<n and 0<=ny<n:
if a[nx][ny] in favo[number][1]:
one += 1
if a[nx][ny] == -1:
two += 1
sorts.append([-one, -two, i, j])
sorts.sort()
#####print(sorts, idx)
ii, jj = sorts[0][2], sorts[0][3]
a[ii][jj] = idx
favo[number].extend([ii, jj]) ###
#for line in a:
# print(line)
## 학생별 만족도 계산
score = 0
for number in range(n*n):
idx, friends, result_i, result_j = favo[number]
cnt = 0
for k in range(4):
nx, ny = result_i+dx[k], result_j+dy[k]
if 0<=nx<n and 0<=ny<n and a[nx][ny] in friends:
cnt += 1
#####print(idx, friends, cnt, (10 ** (cnt-1)))
if cnt != 0: score += (10 ** (cnt-1))
print(score)
- (개선점) 채점되는 시간이 오래 걸린듯 하여 찜찜..
- 비어있는 칸 대상으로 (인접칸 중 좋아하는 학생의 총 수 up/ 인접칸 중 비어있는 칸의 총 수 up/ 행의 번호 down/ 열의 번호 down) 순으로 우선순위를 가지는 부분에 시간을 단축할 조건 한번 고려해보자
- 🙋♂️ max 값을 비교하는 속도나, 정렬하는 속도나 비슷하지 않을까 ?
- 실수를 안하기에는 정렬이 유리하긴 함
Metadata
Metadata
Assignees
Labels
No labels
