22.05.05 추가) PC에서 검색하고 들어오면 화면이 모바일 버전으로 나옵니다.
다른 페이지는 문제가 없는데 어항정리만 뒤에 url에 "/m/" 이 추가되는 것을 확인했습니다.
https://osnim.tistory.com/entry/%EB%B0%B1%EC%A4%80-23291-%EC%96%B4%ED%95%AD%EC%A0%95%EB%A6%AC-%ED%8C%8C%EC%9D%B4%EC%8D%AC 위 사이트로 이동해서 글을 보시면 모바일 화면이 아닌 PC 화면으로 글을 보실수 있을 것입니다
빨리 문제를 해결하겠습니다.
문제 : https://www.acmicpc.net/problem/23291
23291번: 어항 정리
마법사 상어는 그동안 배운 마법을 이용해 어항을 정리하려고 한다. 어항은 정육면체 모양이고, 한 변의 길이는 모두 1이다. 상어가 가지고 있는 어항은 N개이고, 가장 처음에 어항은 일렬로 바
www.acmicpc.net
주의 사항
1. 차를 구할 때 abs 쓰면 중복되어 계산하므로 자기자신에서 주위값 계산하게 하기
이렇게 하면 visited 같은 다른 변수 추가 안해도 됨
2. 정사각배열로 만들어서 방문하지 못하는 곳은 -1로 바꾸기
물고기가 -1마리는 없으니 후에 없는 것 까지 확인 가능
풀이
이전 풀이와 다르게 해당 모듈이 임포트된 경우가 아니라 인터프리터에서 직접 실행된 경우에만, if문 이하의 코드를 돌리라는 명령
__name__ == "__main__":
을 사용하여 코드를 작성해보았습니다.
기능이나 목적을 함수로 잘게 나누어 가독성과 유지보수를 높이는 코드를 구현하고 싶어 위와 같이 새롭게 코딩을 해보았습니다.
먼저 문제를 천천히 읽어보면서 중요한 조건은 남기고 필요없는 부분은 가감히 삭제하여 수월하게 구현을 하려고 다음과 같이 문제 요약을 했습니다.
"""
어항 물고기 1마리 이상, 배열 물고기 수
어항을 한 번 정리하는 과정
2. 어항 쌓기
가장 왼쪾에 있는 어항을 그 오른쪽 어항 위에 올려 놓음
2개 이상 쌓인 어항, 90도 시계 방향 회전, 바닥 왼쪽 어항 위에 공중 부양된 어항중 가장 왼쪽에 있는 어항 존재
위 2 번 과정을 공중 부양 시킨 어항중 가장 오른 쪽에 있는 어항의 아래 바닥에 있는 어항이 있을 때 까지
3. 물고기 수 조절
d = (모든 인접한 두 어항 차이) // 5
d > 0:
두 어항 중 물고기 많은 곳에 있는 d마리 물고기 > 적은곳
이 과정 모든 인접한 칸에 대해 동시 발생
4. 2 번 과정 다시
5. 일렬로 만들기
6. 2번 쌓기
가운데를 중심으로 N/2개를 공중 부양시켜 전체를 시계 방향으로 180도 회전 시킨 다음, 오른쪽 N/2개
두 번 반복 (두 번 반복 하면 바닥에 있는 어항의 수는 N/4개)
"""제출 코드
''__main__" 부분
if __name__ == "__main__":
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
N, K = map(int, input().split())
fishes = list(map(int, input().split()))
op = 0
while max(fishes) - min(fishes) > K:
op += 1
fishes = solve(fishes, N)
print(op)실제 함수들이나 기능들이 작동하는 solve() 부분
def solve(fishes, N):
fishes = fillFish(fishes, N)
fishes = stackBowl1(fishes, N)
fishes = stackBowl2(fishes, N)
"""
물고기가 가장 많이 들어있는 어항과 가장 적게 들어있는 어항의 물고기 수 차이가 K 이하가 되려면
어항을 몇 번 정리해야하는지 구해보자.
"""
return fishes한 마리 채우는 부분
def fillFish(fishes, N):
# 물고기 수 가장 적은 어항에 물고기 한마리 넣음
# if 여러개 >
# 모두 1마리 넣음
minCnt = min(fishes)
for i in range(N):
if fishes[i] == minCnt:
fishes[i] += 1
return fishes물고기를 채우고 다시 일렬로 하는 부분
def stackBowl1(fishes, N):
'''
2. 어항 쌓기
가장 왼쪽에 있는 어항을 그 오른쪽 어항 위에 올려 놓음
2개 이상 쌓인 어항, 90도 시계방향 회전, 바닥 왼쪽 어항위에 공중부양된 어항 중
가장 왼쪽에 있는 어항 존재
위 2 번 과정을 공중부양 시킨 어항 중
가장 오른쪽에 있는 어항의 아래 바닥에 있는 어항이 있을 때 까지
'''
# 처음 회전 부분
bowl = fishes[:]
rot = [[bowl[0]], [bowl[1]]]
# 앞에서 부터 h 만큼 잘라내기
bowl = bowl[2:]
# 첫번째 회전 이후
while True:
h = len(rot) # 높이
w = len(rot[0]) # 밑변
# 남은 길이 - 높이 >= 0
if len(bowl) - h >= 0:
# 회전 == 떼어내서 회전 >
# 회전 배열 배열 > 밑변 높이 바뀜
temp = [[0] * h for _ in range(w)]
for i in range(0, w):
for j in range(h):
temp[i][j] = rot[h - 1 - j][i]
# 밑에 넣기
rot = temp + [bowl[:h]]
# 앞에서 부터 h 만큼 잘라내기
bowl = bowl[h:]
else:
rot[-1] = rot[-1] + bowl
break
# 사각 행렬 만들게 -1 붙임 # 불가능한 곳
for i in range(len(rot)-1):
rot[i].extend([-1] * (len(rot[-1])-len(rot[i])))
'''
d = (모든 인접한 두 어항 차이) // 5
d > 0:
두 어항 중 물고기 많은 곳에 있는 d마리 물고기 > 적은곳
이 과정 모든 인접한 칸에 대해 동시 발생
'''
r = len(rot)
c = len(rot[-1])
temp = [[0]*c for _ in range(r)]
for x in range(len(rot)):
for y in range(len(rot[x])):
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if nx < 0 or nx >= len(rot) or ny < 0 or ny >= len(rot[x]):
continue
if rot[nx][ny] == -1:
continue
d = (rot[x][y] - rot[nx][ny])// 5
if d > 0:
if rot[x][y] < rot[nx][ny]:
temp[x][y] += d
temp[nx][ny] -= d
elif rot[nx][ny] < rot[x][y]:
temp[nx][ny] += d
temp[x][y] -= d
for i in range(r):
for j in range(c):
if rot[i][j] != -1:
rot[i][j] += temp[i][j]
# 한 줄로 만들기
'''
어항 다시 일렬로
가장 왼쪽에 있는 어항부터, 가장 아래쪽에 있는 어항 순
'''
#r = len(temp[0])
cnt = 0
bowl = []
for c in range(len(rot[0])):
for r in range(len(rot)-1, -1, -1):
#값을 변경했을 때만
if rot[r][c] != -1:
bowl.append(rot[r][c])
fishes = bowl[:]
return fishes두번째 어항을 쌓고 다시 일렬로 피는 부분
def stackBowl2(fishes, N):
"""
가운데를 중심으로 N/2개를 공중 부양시켜 전체를 시계 방향으로 180도 회전 시킨 다음, 오른쪽 N/2개
두 번 반복
두 번 반복 하면 바닥에 있는 어항의 수는 N/4개
"""
left = list(reversed(fishes[:(N//2)]))
right = fishes[N//2:]
stackbowl = [left] + [right]
left = [[0]*(N//4) for _ in range(2)]
right = [[0]*(N//4) for _ in range(2)]
for i in range(2):
for j in range(N//2):
if j < N//4:
left[i][j] = stackbowl[i][j]
else:
right[i][j-(N//4)] = stackbowl[i][j]
# left만 180도 회전
left = list(reversed(left))
leftup = list(reversed(left[0]))
leftdown = list(reversed(left[1]))
left = [leftup] + [leftdown]
stackbowl = left + right
r = 4
c = N//4
temp = [[0]*c for _ in range(r)]
for x in range(r):
for y in range(c):
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if nx < 0 or nx >= r or ny < 0 or ny >= c:
continue
d = (stackbowl[x][y] - stackbowl[nx][ny])// 5
if d > 0:
if stackbowl[x][y] < stackbowl[nx][ny]:
temp[x][y] += d
temp[nx][ny] -= d
elif stackbowl[nx][ny] < stackbowl[x][y]:
temp[nx][ny] += d
temp[x][y] -= d
for x in range(r):
for y in range(c):
stackbowl[x][y]+= temp[x][y]
bowl = []
for c in range(N//4):
for r in range(3, -1, -1):
bowl.append(stackbowl[r][c])
fishes = bowl[:]
return fishes
후기
솔직히 2시간 동안 제 스스로 절대 못풀 것 같아서 답지보고 어떻게 푸는지 확인하고 다시 풀어봤는데도 안풀려서 답지 보면서 풀었네요..ㅜㅜ 특히 공중 부양할 때 멘붕오고 정사각 행렬이 아닌 깨진 타일 모양이라 너무 어려웠네요
저는 아직 문제를 있는 그대로 구현하는 것보단 약간 바꿔서 컴퓨터가 계산하는 방식으로 변환시키는게 아직도 어려운 것 같아요
그 와중에 jh05013님의 정답코드가 정말 많이 도움되었습니다.
제 코드가 깔끔하지는 않지만 그래도 제 스타일을 유지한 채 정답을 맞은 것만으로도 기쁘네요
이 문제를 풀면서 제가 놓치거나 약했던 부분을 남겨보려고 합니다.
- 정사각배열을 시계방향이나 반시계방향으로 회전시키는 방법 암기 (반 시계는 상어 중학교)
- 시계: temp[i][j] = rot[h - 1 - j][i]
- 반 시계: temp[i][j] = arr[j][N - 1 - i]
- 최솟값을 찾을 때, index로 하나하나 접근하고 비교하며 찾는 방법을 min 이용하기
- 리스트 역순으로 바꾸기 left = list(reversed(fishes[:(N//2)]))
- 원소를 각 행에 추가하는 방법은 + 아닌 extend로 하기 (extend 는 대입이 실행하면 알아서 바뀜)
rot[i].extend([-1] * (len(rot[-1])-len(rot[i])))'ProblemSolving > 구현, 시뮬레이션, 완전탐색' 카테고리의 다른 글
| 프로그래머스 주차 요금 계산(파이썬) (0) | 2022.05.19 |
|---|---|
| 백준 23289 온풍기 안녕! (파이썬) (0) | 2022.04.28 |
| 백준 23290 마법사 상어와 복제 (파이썬) (0) | 2022.04.25 |
| 백준 23288 주사위 굴리기 2 (파이썬) (0) | 2022.04.23 |
| 백준 21610 마법사 상어와 비바라기 (파이썬) (0) | 2022.04.23 |