사용한 알고리즘/자료구조
- 델타를 이용한 2차원 배열 탐색
- counter sort
- 해시 테이블(딕셔너리)
접근한 방법
학생의 위치를 정할 때마다
- 모든 좌표를 순회하며
- 주위 4 칸의 좌표 정보를 확인하는
브루트포스 알고리즘으로도 정답 처리를 받을 수 있습니다. 하지만 이런 브루트포스 방식은 O(4*(N**2))의 시간 복잡도를 가진, 굉장히 비효율적인 알고리즘입니다.
A학생의 자리를 배정한다고 생각해봅시다.
A학생이 좋아하는 학생들 중 한 명 이상이 이미 교실에 앉아있다고 하면, 우리는 이 학생이 좋아하는 학생들 근처 자리들만 조회한 후 우선순위를 계산하면 됩니다.
이 연산을 위해 딕셔너리를 활용합니다.
딕셔너리는 두 개를 사용합니다.
- 각 학생이 좋아하는 학생들의 정보를 담은 딕셔너리
- 학생 '주변 자리 좌표'를 담은 딕셔너리
아래의 순서대로 학생들을 자리에 배치합니다.
- 특정 학생이 좋아하는 학생들이 이미 교실에 배치되어있는지 확인.
- 만약 배치되었다면, 이들 옆 자리끼리 우선순위를 비교하여 학생을 배치.
- 만약 배치되지 않았다면, 다음 조건(빈 자리가 가장 많은 곳)을 고려하여 학생을 배치.
- 학생을 배치한 후 딕셔너리에 '주변 자리 정보'를 업데이트.
어려웠던 점
구현량이 많은 문제를 풀어보는게 처음이라 상당히 까다로웠습니다.
느낀 점
코드를 작성하면서 주석을 잘 달아야 하는 이유를 아주 잘 느낄 수 있었습니다. 처음부터 계획을 잘 세우지 않았다면 정말 많이 헤맸을 것 같습니다.
객체 지향의 장점 또한 많이 느꼈습니다. 단일 함수에서 모든 연산을 처리하려다보니 변수명 짜기가 어려웠습니다.
개선할 수 있는 점
유사한 로직(2차원 좌표 탐색, 우선도별 counter sort)이 상당히 많이 등장합니다. 이를 함수화시켰다면 훨씬 깔끔하고 정갈하게 풀이할 수 있었을 것이라고 생각합니다. 코드도 200줄에 달해 가독성이 떨어져 아쉽습니다.
풀이했을 당시의 백준 티어
2021-10-11, 골드2
실행시간, 메모리, 언어
92ms, 29200kb, Python3
현재(2021-10-19) 기준 python 언어 계열 기준 실행시간 2등인 풀이입니다.
from sys import stdin
def find_seat(student_num, liked_students):
"""
학생 번호 student_num,
좋아하는 학생들 목록 liked_student,
두 개를 인자로 받습니다.
1. 지금 지목한 학생이 좋아하는 학생들의 옆자리 위치 정보를 조회.
2. 좋아하는 학생들과 가장 많이 인접할 수 있는 동시에 옆 자리가 가장 많이 비어있는 자리를 조회 후 삽입.
3. 2.에서 함수가 종료되지 않을 경우, 빈 자리와 가장 많이 인접한 자리에 삽입.
"""
# 1. 현재 학생이 좋아하는 학생들의 옆자리를 탐색.
# 좋아하는 학생들 목록을 counter sort 할 리스트.
# index + 1 == 얼마나 많은 선호 학생들과 인접해서 앉을 수 있는가.
seat_with_friends = [[] for _ in range(4)]
# 1) 좋아하는 학생들 전부를
for liked_student in liked_students:
# 딕셔너리에서 검색, 그들의 '옆자리' 정보를 가져옵니다.
seat_checker = student_location_dict.get(liked_student) # 상하좌우 위치들만 가져옴.
if seat_checker is None: # 선호하는 학생이 딕셔너리에 없다면 == 아직 안 앉았으면
continue # 무시하고 다음 좋아하는 학생 조회.
for spot in seat_checker: # 좋아하는 학생들 옆자리 모두를 조회.
if seat_table[spot[0]][spot[1]]: # 자리에 이미 누군가 앉아있다면
continue # 무시하고 다음 자리 조회.
for i in range(4): # 나온 횟수에 따라 app...3, 2, 1 0에 들어감.
if spot not in seat_with_friends[i]:
seat_with_friends[i].append(spot)
break
# 2. 현재 학생을 조건에 맞게 배치
for i in range(3, -1, -1): # 위의 1. 에서 counter sort 해둔 자리표를 조회.
# 2-1. 조건에 가장 잘 부합하는 자리 검출.
if seat_with_friends[i]: # 만약에 앉을만 한 자리가 있다면
seat_friend_n_space = [[] for _ in range(4)] # 각 자리를 전부 조회해 인접한 빈 칸의 숫자별로 counter sort.
for seat in seat_with_friends[i]: # 1. 에서 했던 로직과 동일한 방식으로 옆자리 빈칸을 조회할 것임.
space = 0 # 빈 칸의 갯수를 받을 변수.
for direction in range(4): # 4방향을 순회하며
new_y = seat[0] + DY[direction]
new_x = seat[1] + DX[direction]
if 0 <= new_y < N and 0 <= new_x < N\
and not seat_table[new_y][new_x]: # 비어있다면
space += 1 # '비어있음' 변수에 1 가산.
seat_friend_n_space[space].append(seat) # counter sort
# 2-2. 실제로 배치
for j in range(3, -1, -1):
if not seat_friend_n_space[j]:
continue
seat_friend_n_space[j].sort(key=lambda x: (x[0], x[1])) # (행/열 번호 오름차순으로 정렬 후 )
seat_y, seat_x = seat_friend_n_space[j][0] # 가장 적절한 좌석 좌표를 가져옴.
seat_table[seat_y][seat_x] = student_num # 학생을 배치 배치
# 2-3. 추후 연산을 위한 인접 좌표 딕셔너리 제작.
seats_around = [] # 딕셔너리 작업용 리스트
for direction in range(4): # 4방향을 순회하며
new_y = seat_y + DY[direction]
new_x = seat_x + DX[direction]
if 0 <= new_y < N and 0 <= new_x < N \
and not seat_table[new_y][new_x]: # 정상이면
seats_around.append((new_y, new_x)) # seats_around 에 집어넣음.
if seats_around: # 공집합이 아니라면
student_location_dict[student_num] = seats_around # 딕셔너리에 삽입.
return # 잘 앉았으니 함수 종료.
# 3. 좋아하는 애들 있는 자리에 놓을 수 없으면.
# 모든 좌표를 조회하며
# 각 좌표를 '옆의 빈자리 수'를 기준으로 counter sort.
# 3-1. 전체 좌표를 순회하며 '빈 칸이 많은' 곳 찾기.
empty_seat = [[] for _ in range(5)] # 카운터 소트를 위한 리스트
found_four = False
for i in range(N):
for j in range(N):
if not seat_table[i][j]:
space = 0
for direction in range(4): # 4방향을 순회하며
new_y = i + DY[direction]
new_x = j + DX[direction]
if 0 <= new_y < N and 0 <= new_x < N and not seat_table[new_y][new_x]: # 비어있으면
space += 1 # 공간 1 추가.
empty_seat[space].append((i, j)) # 정렬 완료.
if space == 4: # 만약 주위에 빈 공간이 4개라면
found_four = True # 스위치 켜고
break # 반복문 종료
if found_four: # 반복문 종료
break # 해설: 행 우선 순회하는 중이므로 빈 공간이 4개인 지점을 찾으면
# 이 곳에 바로 배치하면 된다.
# 3-2 연산 후 '적절한 곳 찾아 배치'
for i in range(4, -1, -1):
if empty_seat[i]: # 만약에 값이 있으면
empty_seat[i].sort(key=lambda x: (x[0], x[1])) # 조건에 맞게 정렬 후
seat_y, seat_x = empty_seat[i][0]
seat_table[seat_y][seat_x] = student_num # 배치
seats_around = [] # 딕셔너리 작업용 리스트
for direction in range(4): # 4방향을 순회하며
new_y = seat_y + DY[direction]
new_x = seat_x + DX[direction]
if 0 <= new_y < N and 0 <= new_x < N and not seat_table[new_y][new_x]: # 정상이면
seats_around.append((new_y, new_x)) # seats_around 에 집어넣음.
if seats_around:
student_location_dict[student_num] = seats_around
return # 잘 앉았으니 함수 종료.
# 디렉션 볼 때 상 좌 우 하 순으로 본다.
DX = (0, -1, 1, 0)
DY = (-1, 0, 0, 1)
# 1. 입력
N = int(stdin.readline())
# 2. 선언
# 2-1. 실제 좌석 배치표.
seat_table = [[0] * N for _ in range(N)]
# 2-2. 학생들의 옆자리 좌표계 딕셔너리
student_location_dict = dict()
# 2-3. 학생별 선호 학생 딕셔너리
student_likes_dict = dict()
# 3. 연산
# 3-1. 자리 배치
for every_students in range(N**2):
# 3-1. 연산부 입력
# 1) 학생 정보 입력
student_info = tuple(map(int, stdin.readline().split()))
student_number = student_info[0]
# 2) 학생별 선호도 튜플을 딕셔너리에 삽입.
student_likes_dict[student_number] = student_info[1:]
# 3) 자리배치. 자세한 내용은 위의 'find-seat' 함수를 참조.
find_seat(student_number, student_info[1:])
# 3-2. 만족도 조사
# 1) 만족도 조사를 위한 변수 선언.
satisfaction = 0
satisfaction_table = (0, 1, 10, 100, 1000)
# 2) 배열 순회
for i in range(N):
for j in range(N):
# (1) 학생 정보 조회
student = seat_table[i][j] # 모든 학생들을 조회하여
favorite_ones = student_likes_dict.get(student) # 그들이 좋아하는 학생들의 정보를 얻어옴.
num_of_favorites = 0 # 좋아하는 학생들이 근처에 얼마나 있는지 확인할 카운터 변수
# (2) 근처에 좋아하는 학생들이 얼마나 있는지 조회
for drc in range(4): # 4방향 모두 조회
new_y = i + DY[drc]
new_x = j + DX[drc]
# a. 인덱스 오버플로우가 일어나지 않고, 옆자리에 favorite one이 앉아있다면
if 0 <= new_y < N and 0 <= new_x < N \
and seat_table[new_y][new_x] in favorite_ones:
num_of_favorites += 1 # 좋아하는 학생 변수 1개 가산.
# (3) 좋아하는 학생들의 인원수에 맞게
# 결과값에 특정한 값을 더해줌.
satisfaction += satisfaction_table[num_of_favorites]
# 4. 출력
print(satisfaction)'BOJ > 구현' 카테고리의 다른 글
| 17070. 파이프 옮기기 - DP + 비트마스킹. 파이썬 (0) | 2021.10.22 |
|---|---|
| 14500. 테트로미노 -브루트 포스, 구현, 시뮬레이션. [파이썬] (0) | 2021.10.15 |
| 14503. 로봇청소기 - 시뮬레이션, 구현 (0) | 2021.09.27 |
| 3019. 뱀 (0) | 2021.09.15 |