백준 23291 : 어항 정리

https://www.acmicpc.net/problem/23291

23291번: 어항 정리

https://github.com/HPYoo/swcodingtest/commit/225f557725f763ae36b7669bf4c539809fa23c94

sw coding 23291 update(Baekjoon) · HPYoo/swcodingtest@225f557

1. 구현할 것이 굉장히 많음

 총 6가지 항목으로 나누어서 구현을 하였다. 입력받은 배열은 손상되지 않게 복사해서 사용했고, 리스트를 새로 구성할 때 정방형이 아닌 각 행마다 크기가 다른 리스트를 하나의 배열로 입력 받았기 때문에 중간 중간에 예외처리를 필수적으로 해줘야했다.

 -1) 물고기 집어넣기 : 최소값 찾아서 하나씩 더해주면 끝

 -2) 어항쌓기 : temp로 제일 왼쪽 어항을 가져온 다음에 append 하여 temp를 리턴하면 된다.

 -3) 2개 이상 쌓여있는 어항을 모두 떼어서 시계 방향으로 90도 회전(rotate 함수) : 

  Row 개수가 제일 많은 Column 들의 경우에 대해서 다음 그림과 같이 번호 순서대로 새 리스트를 생성하여 append 해주면 90도 회전한 것과 같은 모습이 된다.

 -4) 물고기 수 조절하기 : 리스트 모양 때문에 dx, dy 를 활용한 위치 이동에서 문제가 발생한다. 2차원 배열 안에서 각 리스트의 크기가 다르기 때문에 try & except으로 예외처리를 해준다. 

 -5) 다시 눕히기 : 눕히는 것 또한 맨 아래 리스트에서 위로 진행해주면 쉽게 구현할 수 있다.

 -6) 반씩 나눠 돌리기 : 90도 회전 시키는 것과 크게 다르지 않다. 하지만, 180도 회전이기 때문에 맨 아래 리스트부터 역으로 진행하되 리스트 안에서는 순차적으로 숫자를 뽑아내면된다.

 이렇게 각각 함수를 만들어두고 반복문으로 작동시키면 이해하기가 수월하다.

2. 전체 코드

메모리 : 115468 KB, 시간 : 148 ms, 풀이시간 : 103min 34s

N, K = map(int, input().split())
# 가장 많은 것과 적은 것이 K 차이가 되어야함.
board = list(map(int, input().split()))
# Ex) arr = [5, 2, 3, 14, 9, 2, 11, 8]
# 1 단계 : 물고기 집어넣기
def put_fish(arr):
    minValue = min(arr)
    for i in range(len(arr)):
        if arr[i] == minValue :
            arr[i] += 1
    return arr

# 2 단계 : 어항 쌓기
def pile(arr):
    temp = [[arr[0]]]
    del arr[0]
    temp.append(arr)
    return temp

# 3 단계 : 2개 이상 쌓여있는 어항을 모두 떼어서 시계 방향으로 90도 회전
def rotate(arr):
    while True :
        temp = []
        minValue = len(arr) + 1
        for i in range(len(arr)):
            minValue = min(minValue, len(arr[i])) # Column
        if len(arr) > len(arr[-1]) - minValue : break
        for j in range(minValue): # Column
            sample = []
            for i in range(len(arr)-1, -1, -1): # Row
                sample.append(arr[i][j])
            temp.append(sample)
        temp.append(arr[-1][minValue : ])
        arr = temp.copy()
    return arr

# 4단계 물고기 수 조절하기
def arrangement(arr):
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    temp = []
    for i in range(len(arr)):
        for j in range(len(arr[i])) :
            x, y = i, j
            for d in range(4):
                nx = x + dx[d]
                ny = y + dy[d]
                if 0 <= nx < len(arr) and 0 <= ny < len(arr[i]) :
                    try :
                        diff = abs(arr[x][y] - arr[nx][ny]) // 5
                        if arr[nx][ny] > arr[x][y] :
                            temp.append([x, y, diff])
                            temp.append([nx, ny, -diff])
                    except : continue
    for x, y, diff in temp :
        arr[x][y] += diff
    return arr

# 5단계 : 다시 눕히자
def rescale(arr):
    temp = []
    for j in range(len(arr[-1])) :
        for i in range(len(arr) -1, -1, -1):
            try :
                temp.append(arr[i][j])
            except : continue
    return temp

def rotate2(arr):
    size = int(len(arr)/2)
    temp = [[arr[i] for i in range(size-1, -1, -1)], arr[size : ]]
    size //= 2
    new_array = []
    for j in range(len(temp)-1, -1, -1):
        sample = []
        for i in range(size -1, -1, -1):
            sample.append(temp[j][i])
        new_array.append(sample)
    new_temp = []
    for i in range(len(temp)):
        new_temp.append(temp[i][size : ])
    new_array += new_temp
    return new_array

def solve():
    it = 0
    array = board.copy()
    while True :
        if max(array) - min(array) <= K : break
        array = put_fish(array)
        array = pile(array)
        array = rotate(array)
        array = arrangement(array)
        array = rescale(array)
        array = rotate2(array)
        array = arrangement(array)
        array = rescale(array)
        it += 1
    return it

print(solve())