문제 링크
https://www.acmicpc.net/problem/23291
🕒 Python 풀이시간: 1시간 30분
n,k=map(int,input().split())
arr=[list(map(int,input().split()))]
dx=[0,1]
dy=[1,0]
def plusMinimum(arr):
minValue=min(arr[0])
for i in range(len(arr[0])):
if arr[0][i]==minValue:
arr[0][i]+=1
def adjust(arr):
new_arr=[[0]*len(arr[0]) for _ in range(len(arr))]
for i in range(1,len(arr)):
arr[i]+=[0]*(len(arr[0])-len(arr[i]))
for i in range(len(arr)):
for j in range(len(arr[i])):
if arr[i][j]==0:
continue
for k in range(2):
nx=i+dx[k]
ny=j+dy[k]
if 0<=nx<len(arr) and 0<=ny<len(arr[0]) and arr[nx][ny]!=0:
d=abs(arr[nx][ny]-arr[i][j])//5
if d>0:
if arr[nx][ny]>arr[i][j]:
new_arr[i][j]+=d
new_arr[nx][ny]-=d
else:
new_arr[i][j]-=d
new_arr[nx][ny]+=d
for i in range(len(arr)):
for j in range(len(arr[i])):
new_arr[i][j]+=arr[i][j]
for i in range(len(new_arr)):
idx=len(new_arr[i])
for j in range(len(new_arr[i])):
if new_arr[i][j]==0:
idx=j
break
new_arr[i]=new_arr[i][:idx]
return new_arr
def makeLine(arr):
for i in range(1,len(arr)):
arr[i]+=[0]*(len(arr[0])-len(arr[i]))
new_arr=[]
for j in range(len(arr[0])):
for i in range(len(arr)):
if arr[i][j]!=0:
new_arr.append(arr[i][j])
return [new_arr]
def levitation(arr):
while True:
h=len(arr)
w=len(arr[0])
smallW=len(arr[-1]) if len(arr)>1 else 1
if w-smallW<h:
return arr
new_arr=[arr[0][smallW:]]
for j in range(smallW-1,-1,-1):
tmp=[]
for i in range(h):
tmp.append(arr[i][j])
new_arr.append(tmp)
arr=new_arr
def halfLeviation(arr):
tmp=arr[0][0:len(arr[0])//2]
arr.append(tmp[::-1])
arr[0]=arr[0][len(arr[0])//2:]
for i in range(1,-1,-1):
arr.append(arr[i][len(arr[0])//2-1::-1])
arr[i]=arr[i][len(arr[0])//2:]
answer=0
while True:
answer+=1
plusMinimum(arr)
# 공중부양 반복
arr=levitation(arr)
# 조절
arr=adjust(arr)
# 일렬
arr=makeLine(arr)
# N/2 * 2
halfLeviation(arr)
# 조절
arr=adjust(arr)
# 일렬
arr=makeLine(arr)
maxValue=-1
minValue=100000
for i in range(len(arr)):
maxValue=max(maxValue,max(arr[i]))
minValue=min(minValue,min(arr[i]))
if maxValue-minValue<=k:
break
print(answer)마법사 상어의 어항 정리 시뮬레이션! 🐠✨
마법사 상어가 이번엔 어항 정리를 하는 과정을 시뮬레이션 하는 문제이다. 각 어항의 최소값과 최댓값의 차이가 K이하 이면 종료되는 시점의 횟수를 구하는 것이다.
배열의 인덱스를 자유자제로 다루는데 있어서 꽤나 까다로운 문제이다. 처음에는 단순히 최솟값을 찾아서 해당 최솟값의 어항의 물고기를 +1 해준다.
두번째는 어항을 쌓는 과정이다. 첫번째 1칸을 제외한 나머지의 경우는 현재 쌓여있는 어항의 가로폭과 높이를 이용해서 해당 어항을 읽어와서 그대로 배열에 넣어주면 된다. 이 때, 남은 폭이 현재 어항의 높이보다 작다면 더 이상 쌓을 수 없으므로 종료시킨다.
이제 중간 중간에 있는 물고기 수를 조절하는 과정이다. 이 때, 각 층의 높이가 다르기 때문에 전체 배열의 행과 열의 높이를 맞춰준 후, 빈칸은 0으로 만들고 진행하였다. 이 때, 0이 아닌 칸에 대해서만 각 인접한 어항을 비교하며 또한 한쪽 방향으로만 해주어야 반복되어 물고기의 이동이 일어나지 않는다. 나의 경우는 행과 열이 증가하는 방향으로만 탐색해주었다. 동시 진행이므로 전부 이동의 증감을 구한 후, 반영해주었다.
이제 일렬로 맞추는 과정인데 이 건 단순히 읽어오는 순서에 유의하여서 읽어오면 된다. 이 때도, 행과 열의 길이가 각 다른 배열이기 때문에 나머지 칸이 0인 배열로 만들어준 후, 0을 제외한 칸만 읽어주었다.
이제 반으로 두번 쌓는 공중부양만 남았기 때문에 이를 처리해주면 된다. 이 때는 1층인 어항에 쌓는것과 읽어오는 것이 다르기에 먼저 반으로 쌓아올린 후 나머지를 처리하였다. 먼저 반으로 처리할 때는 단순히 반만 읽어와서 reverse하여 쌓아올렸고 또 나머지 반의 경우는 한층씩 반을 읽어서 쌓는 식으로 reverse하여 올려주었다.
이렇게 Python으로 백준의 "어항 정리" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊
