작일 삼성 SW 역량테스트를 마친후 듣는 수업이 알고리즘 수업...
감회가 새로웠다.
어제 삼성문제는 난도가 엄청 높진 않았지만, 특정부분에서 디버깅이 너무 오래걸리는바람에 완벽한 1솔을 못했으므로 상심이 컸다.
(시험이 4시간이 되고부터는 해야할 테스크가 제법 많아졌다)
평소에 잘풀던 구현과 시뮬레이션, 최단거리에 행렬회전,
눈감고도 풀던 문제일 정도로 자주 연습해왔는데 사각형 범위 구하는데에 실수가 있었던 것 같다.
금주 토요일에 LG전자 코테또한 있으니 사실 상심할 시간은 없다.
오늘은 프로그래머스 데이터엔지니어링 데브코스 수업 첫날이었다.
내용이 알고리즘이라 편하게 들었고, 남은 시간은 구현문제를 한문제 풀었다 (미련이 남아서)
문제요약 : 어항 어레이를 2차원으로 늘려 회전하고 주변값과 연산 후 다시 1차원으로
문제는 여섯 단계로 나뉘었다.
-
물고기의 수가 가장 적은 어항에 물고기를 한 마리 넣는다
-
가장 왼쪽에 있는 어항을 그 어항의 오른쪽에 있는 어항의 위에 올려 놓는다.
-
2개 이상 쌓여있는 어항을 모두 공중 부양시킨 다음, 전체를 시계방향으로 90도 회전시킨다. 이후 공중 부양시킨 어항을 바닥에 있는 어항의 위에 올려놓는다.
-
공중 부양 작업이 모두 끝나면, 어항에 있는 물고기의 수를 조절한다.모든 인접한 두 어항에 대해서, 물고기 수의 차이를 구한다. 이 차이를 5로 나눈 몫을 d라고 하자. d가 0보다 크면, 두 어항 중 물고기의 수가 많은 곳에 있는 물고기 d 마리를 적은 곳에 있는 곳으로 보낸다.
-
공중 부양 작업을 해야 한다. 이번에는 가운데를 중심으로 왼쪽 N/2개를 공중 부양시켜 전체를 시계 방향으로 180도 회전 시킨 다음, 오른쪽 N/2개의 위에 놓아야 한다. 이 작업은 두 번 반복해야한다.
-
다시 위에서 한 물고기 조절 작업을 수행하고, 바닥에 일렬로 놓는 작업을 수행한다.
-
물고기가 가장 많이 들어있는 어항과 가장 적게 들어있는 어항의 물고기 수 차이가 K 이하가 될때까지 반복한다.
구현은 항상 요구가 길어 머리가 아프지만, 실제로 풀다보면 명확하게 기능이 나누어져 있어서 별로 어렵지 않다. (근데도 시험장에선...)
결과는 아래와 같다.
import copy
def add_fish(bowl: list):
min_fish = min(bowl)
for idx, fish in enumerate(bowl):
if fish == min_fish:
bowl[idx] += 1
return bowl
# 한번 회전해서 쌓기위한 준비
def find_bowl(grid):
# 탐색 해야하는 층수 계산
# 남은 부분의 길이가 길면 temp_grid 반환
temp_grid = grid.copy()
start_col = 0
N = len(grid)
if grid[-1][0] is not None:
grid[-2][1], grid[-1][0] = grid[-1][0], None
return grid, None, None, None
for j in range(N):
if grid[-1][j] is not None:
start_col = j
break
array = []
# 회전시킬 어레이 찾기
# print(grid[-4:])
for x in range(N-1):
flag = 0
temp = []
for y in range(start_col, N-1):
if grid[x][y] is not None:
temp.append(grid[x][y])
flag = 1
grid[x][y] = None
else:
if flag:
array.append(temp)
break
rest_len = len([x for x in grid[-1] if x is not None])
# print(array)
if array == [] or rest_len - len(array[0]) < len(array) + 1:
return temp_grid, array, start_col, None
else:
col_len = len(array[0])
last_line = []
for last in range(start_col, start_col + col_len):
last_line.append(grid[-1][last])
grid[-1][last] = None
array.append(last_line)
return grid, array, start_col, rest_len
def rotate_array(array: list):
n_row = len(array)
n_col = len(array[0])
new_array = [[0] * n_row for _ in range(n_col)]
for j in range(n_col):
for i in range(n_row):
new_array[j][n_row-1-i] = array[i][j]
return new_array
def add_bowl(grid, array, start_col):
new_bowl = rotate_array(array)
start_row = (len(grid)-1) - len(new_bowl)
for new_row in range(len(new_bowl)):
for new_col in range(len(new_bowl[0])):
grid[start_row+new_row][start_col+len(array[0])+new_col] = new_bowl[new_row][new_col]
bowl = []
for x in range(start_row, len(grid)):
row = []
for y in range(start_col+len(array[0]), len(grid)):
row.append(grid[x][y])
bowl.append(row)
# print(bowl)
return grid, bowl
def arrange_fish(bowl):
# 한번씩만 연산하므로, 오른쪽과 아래만 보면됨
dx, dy = (0, 1), (1, 0)
temp = [[0] * len(bowl[0]) for _ in range(len(bowl))]
for x in range(len(bowl)):
for y in range(len(bowl[0])):
if bowl[x][y] is None:
continue
else:
for i in range(2):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < len(bowl) and 0<= ny <len(bowl[0]):
if bowl[nx][ny] is not None:
d = abs(bowl[x][y] - bowl[nx][ny]) // 5
if d > 0:
if bowl[x][y] > bowl[nx][ny]:
temp[x][y] -= d
temp[nx][ny] += d
else:
temp[x][y] += d
temp[nx][ny] -= d
# print("temp :",temp)
for i in range(len(bowl)):
for j in range(len(bowl[0])):
if bowl[i][j] is not None:
bowl[i][j] += temp[i][j]
return bowl
def flatten(bowl):
flat_bowl = []
for j in range(len(bowl[0])):
for i in range(len(bowl)-1, -1, -1):
if bowl[i][j] is not None:
flat_bowl.append(bowl[i][j])
return flat_bowl
def rotate_twice(bowl):
result = []
# 1번 회전
bowl1, bowl2 = bowl[:len(bowl)//2], bowl[len(bowl)//2:]
result.append(bowl1[::-1])
result.append(bowl2)
# 2번 회전
top = []
bottom = []
for i in range(2):
top.append(result[i][:len(result[0])//2])
bottom.append(result[i][len(result[0])//2:])
top_rotate = rotate_array(rotate_array(top))
return top_rotate + bottom
if __name__ == "__main__":
N, K = map(int, input().split())
bowl = list(map(int, input().split()))
# 가상의 공간
T = 0
diff = 999
while True:
if diff <= K:
print(T)
break
T += 1
grid = [[None] * N for _ in range(N - 1)]
bowl = add_fish(bowl)
grid.append(bowl)
trial = 1
while True:
temp_grid = copy.deepcopy(grid)
if trial == 1:
grid, _, _, _ = find_bowl(grid)
else:
grid, array, start_col, rest_len = find_bowl(grid)
if rest_len is None:
grid = temp_grid
break
else:
grid, bowl = add_bowl(grid, array, start_col)
trial += 1
arranged_bowl = arrange_fish(bowl)
flat_bowl = flatten(arranged_bowl)
rotate_bowl = rotate_twice(flat_bowl)
arranged_bowl2 = arrange_fish(rotate_bowl)
bowl = flatten(arranged_bowl2)
diff = max(bowl) - min(bowl)
