[Python] 23291. 어항 정리

 

풀이

순수한 구현 문제.

각 행위에 대한 함수들을 작성하고 한 사이클을 다 작성하면 while 문으로 원하는 값을 얻을 때까지 반복한다.

 

코드

import sys
input = sys.stdin.readline
n, k = map(int, input().split())
temp = list(map(int,input().split()))
arr = []
cnt = 0
for i in range(n):
    arr.append([temp[i]])

while 1:
    def fish_sort():
        global cnt
        min_val = 10000
        max_val = 0
        for i in range(len(arr)):
            # 최소 찾아서 저장해두기
            if arr[i][0] < min_val:
                min_val = arr[i][0]
            if arr[i][0] > max_val:
                max_val = arr[i][0]
        gap = max_val - min_val
        if gap <= k:
            print(cnt)
            exit()
        cnt += 1
        # 정렬 시작        
        # 최소에다가 1씩 더해주기
        for i in range(len(arr)):
            if arr[i][0] == min_val:
                arr[i][0] += 1
        # 끝에 쌓기
        arr[1].append(arr[0].pop())

        bool1 = True
        while bool1:
            start = 0
            # 거꾸로 순회하면서
            for i in range(len(arr)-1,-1,-1):
                # 기둥 발견하다
                if len(arr[i]) >= 2:
                    # 기둥의 높이가 쌓을 바닥보다 크면 안 쌓는다
                    if len(arr[i]) > len(arr)-1-i:
                        bool1 = False
                        break
                    # 찾은 기둥의 인덱스 i의 바로 오른쪽부터 차곡차곡 쌓자
                    while len(arr[i]) > 0:
                        # 기둥 기준으로 옮길 어항의 층번호만큼 오른쪽 바닥에 쌓는다
                        arr[i+len(arr[i])+start].append(arr[i].pop(-1))
                    start += 1

        def fish_num_sort():
            dx, dy = [0,1,0,-1], [-1,0,1,0]
            visited = [[0] * len(arr[i]) for i in range(len(arr))]
            for i in range(len(arr)):
                if 0 < len(arr[i]):
                    for j in range(len(arr)):
                        if j < len(arr[i]):
                            # 현재 영역 값을 변수에 저장해둠
                            num = arr[i][j]
                            for k in range(4):
                                nx = i + dx[k]
                                ny = j + dy[k]
                                if 0 <= nx < len(arr) and 0 <= ny < len(arr[nx]):
                                    # 현재 영역 -5값이 주변보다 크면
                                    if num - 5 >= arr[nx][ny]:
                                        # 주변값과의 차이를 변수에 저장
                                        diff = num - arr[nx][ny]
                                        # 큰 어항에서 작은 어항으로 물고기 옮김
                                        d = diff // 5
                                        visited[i][j] -= d
                                        visited[nx][ny] += d
            for i in range(len(arr)):
                for j in range(len(arr[i])):
                    arr[i][j] += visited[i][j]
        fish_num_sort()

        def spread():
            j = 0
            for i in range(len(arr)):
                for k in range(len(arr[i])):
                    arr[j].append(arr[i].pop(0))
                    j += 1
        spread()

        for i in range(len(arr)//2):
            arr[len(arr)-1-i].append(arr[i].pop())

        for num in range(2):
            for i in range(len(arr)//2, len(arr)//2 + len(arr)//4):
                arr[len(arr)-1-(i-len(arr)//2)].append(arr[i].pop())
        fish_num_sort()
        S = 0
        for i in range(len(arr)):
            while arr[i] and S < len(arr):
                arr[S].append(arr[i].pop(0))
                S += 1
    fish_sort()