Skip to content

(22 복습) 삼성 SW 역량 테스트 기출 문제 / 백준 / 21608번: 상어 초등학교 #142

@sallyy1

Description

@sallyy1

image

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

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions