[python] 어항 정리 - 23291번

빡구현 문제이다

시간복잡도를 생각하지 않아도 되는 여유로운 문제여서 특별한 자료구조를 따로 사용하지는 않고 배열로만 풀었다.

어항 뒤집기 할때가 구현하기 빡세고,

물고기 수 비교해서 옮겨담을 때는 아래와 오른쪽만 비교해줘서 계산해주면 된다. (위랑 왼쪽을 같이 고려해주면 중복때문에 복잡해짐)

깊은복사를 위해 copy모듈을 가져와 사용했다.

파이썬의 슬라이싱 [ : ] 을 이용하면 단순한 1중배열에 경우에 한하여 깊은복사처럼 사용할 수 있지만, 2중배열부터 내부 배열의 주소를 얕은 복사해버리기 때문에 deepcopy를 사용하는 것을 추천한다.

         

import copy
n,k = map(int,input().split())
fishbowl = list(map(int,input().split()))


def juggle(fishbowl):
# def juggle():
    # 테스트
    # fishbowl = [5,2,3,14,9,2,11,8]
    # n = 8
    # k = 7




    # 1. 작은 어항에 물고기 추가하기
    mini = min(fishbowl)
    for i in range(n):
        if fishbowl[i] == mini:
            fishbowl[i] += 1
    
    # 2. 공중부양 쌓기 1
    
    # 미리 한칸 쌓기
    width = 1
    height = 2
    
    
    stacking = [[fishbowl[0]],[fishbowl[1]]]

    fishbowl.pop(0)
    fishbowl.pop(0)

    while True:
        if width*height > n:
            break
        if width==height and width*(height+1) <= n:
            height+=1
            stackingCopy = [['?']*width for i in range(height)]
            

            for y in range(height-1):
                for x in range(width):
                    stackingCopy[x][width-1-y] = stacking[y][x]

            stackingCopy[-1] = fishbowl[:width]

            for i in range(width):
                fishbowl.pop(0)
            
            stacking = copy.deepcopy(stackingCopy)
        elif width+1 == height and (width+1)*height <= n:
            width+=1
            stackingCopy = [['?']*width for i in range(height)]

            for y in range(height):
                for x in range(width-1):
                    stackingCopy[x][height-1-y] = stacking[y][x]
                    

            stackingCopy[-1] = fishbowl[:width]
            for i in range(width):
                fishbowl.pop(0)
            
            stacking = stackingCopy[:]
        else:
            for i in fishbowl:
                stacking[-1].append(i)
            fishbowl = copy.deepcopy(stacking)
            break



    # 3. 공중부양 물고기 수 조절 1
    fishbowlCopy = copy.deepcopy(fishbowl)
    for i in range(len(fishbowl)):
        for j in range(len(fishbowl[i])):
            # 생각해보니 아래 오른쪽만 검사해주고 계산해줘야 중첩이 안됨
            
            # # 위
            # if i%2==0 and i-1>=0 and len(fishbowl[i-1])-1 >= j:
            #     if fishbowl[i][j] > fishbowl[i-1][j]:
            #         gap = (fishbowl[i][j] - fishbowl[i-1][j])//5
            #         fishbowlCopy[i][j] -= gap
            #         fishbowlCopy[i-1][j] += gap
            #     else:
            #         gap = (fishbowl[i-1][j] - fishbowl[i][j])//5
            #         fishbowlCopy[i][j] += gap
            #         fishbowlCopy[i-1][j] -= gap
            # 아래
            if i+1 <= len(fishbowl)-1:
                if fishbowl[i][j] > fishbowl[i+1][j]:
                    gap = (fishbowl[i][j]-fishbowl[i+1][j])//5
                    fishbowlCopy[i][j] -= gap
                    fishbowlCopy[i+1][j] += gap
                else:
                    gap = (fishbowl[i+1][j] - fishbowl[i][j])//5
                    fishbowlCopy[i][j] += gap
                    fishbowlCopy[i+1][j] -= gap
            # # 왼쪽
            # if j-1 >= 0:
            #     if fishbowl[i][j] > sfishbowl[i][j-1]:
            #         gap = (fishbowl[i][j] - fishbowl[i][j-1])//5
            #         fishbowlCopy[i][j] -= gap
            #         fishbowlCopy[i][j-1] += gap
            #     else:
            #         gap = (fishbowl[i][j-1] - fishbowl[i][j])//5
            #         fishbowlCopy[i][j] += gap
            #         fishbowlCopy[i][j-1] -= gap
            # 오른쪽
            if j+1 <= len(fishbowl[i])-1:
                if fishbowl[i][j] > fishbowl[i][j+1]:
                    gap = (fishbowl[i][j] - fishbowl[i][j+1])//5
                    fishbowlCopy[i][j] -= gap
                    fishbowlCopy[i][j+1] += gap
                else:
                    gap = (fishbowl[i][j+1] - fishbowl[i][j])//5
                    fishbowlCopy[i][j] += gap
                    fishbowlCopy[i][j+1] -= gap
    fishbowl = copy.deepcopy(fishbowlCopy)
    # 4. 바닥에 펼치기 1
    fishbowlCopy = []
    for j in range(len(fishbowl[-1])):
        for i in range(len(fishbowl)):
            if len(fishbowl[len(fishbowl)-1-i])-1 >= j:
                fishbowlCopy.append(fishbowl[len(fishbowl)-1-i][j])
    fishbowl = copy.deepcopy(fishbowlCopy)

    # 5. 공중부양 쌓기 2
    # 첫번째 뒤집기
    fishbowlCopy = [[],[]]
    for i in range(int(n/2)):
        fishbowlCopy[0].append(fishbowl[n//2-1-i])
        fishbowlCopy[1].append(fishbowl[i+n//2])
    fishbowl = [[] for _ in range(4)]
    for i in range(int(n//4)):
        fishbowl[0].append(fishbowlCopy[1][n//4-1-i])
        fishbowl[1].append(fishbowlCopy[0][n//4-1-i])
        fishbowl[2].append(fishbowlCopy[0][n//4+i])
        fishbowl[3].append(fishbowlCopy[1][n//4+i])

    # 6. 공중부양 물고기 수 조절 2
    fishbowlCopy = []
    fishbowlCopy = copy.deepcopy(fishbowl)
    for i in range(len(fishbowl)):
        for j in range(len(fishbowl[i])):
            # 아래
            if i+1 <= len(fishbowl)-1:
                if fishbowl[i][j] > fishbowl[i+1][j]:
                    gap = (fishbowl[i][j]-fishbowl[i+1][j])//5
                    fishbowlCopy[i][j] -= gap
                    fishbowlCopy[i+1][j] += gap
                else:
                    gap = (fishbowl[i+1][j] - fishbowl[i][j])//5
                    fishbowlCopy[i][j] += gap
                    fishbowlCopy[i+1][j] -= gap
            # 오른쪽
            if j+1 <= len(fishbowl[i])-1:
                if fishbowl[i][j] > fishbowl[i][j+1]:
                    gap = (fishbowl[i][j] - fishbowl[i][j+1])//5
                    fishbowlCopy[i][j] -= gap
                    fishbowlCopy[i][j+1] += gap
                else:
                    gap = (fishbowl[i][j+1] - fishbowl[i][j])//5
                    fishbowlCopy[i][j] += gap
                    fishbowlCopy[i][j+1] -= gap
    fishbowl = copy.deepcopy(fishbowlCopy)
    
    # 7. 바닥에 펼치기 2
    fishbowlCopy = []
    for j in range(len(fishbowl[-1])):
        for i in range(len(fishbowl)):
            if len(fishbowl[len(fishbowl)-1-i])-1 >= j:
                fishbowlCopy.append(fishbowl[len(fishbowl)-1-i][j])
    fishbowl = copy.deepcopy(fishbowlCopy)
    return fishbowl
    # 8. k값과 최대최소 비교

cnt = 0
while True:
    if max(fishbowl) - min(fishbowl) <= k:
        break
    fishbowl = juggle(fishbowl)
    cnt+=1
    
# print(fishbowl)
print(cnt)