문제
문제가 조금 복잡한데… 제시된 설명이 어렵거나 헷갈리지는 않다. 간략히 보자면 초기 상태에 일렬로 숫자가 써져있는 $N$개의 어항이 있다. 이 어항의 숫자를 조작하는 어항 정리라는 연산이 정의되어 있고, 이를 몇번 해야 어항의 최대값과 최소값의 차이를 $K$ 이하로 만들 것이냐는 문제이다.
접근
당연하지만 구현만 하면 되는데, 설명을 읽어보면 풀기도 전부터 어떻게 구현할까 머리가 지끈거린다. 어항을 막 쌓았다가 내렸다가 돌렸다가 하는데, 나는 각 층별로 하나의 리스트를 사용하였고 리스트 슬라이싱을 활용해서 조작했다. 즉, fishbowl리스트는 [[1층 숫자들...], [2층 숫자들...], ...]꼴의 2차원 리스트이다. 여기서 2층 이상에서의 숫자 갯수는 동일할 수 밖에 없지만, 2층의 숫자 갯수와 1층 숫자개수는 달라질 수 있다. C++로 짜면 이 부분이 귀찮을 것 같아 Python을 골랐다.
먼저 물고기 수가 최소인 어항에 물고기를 넣는 것은 어렵지 않다. 루프의 시작 부분에서 최소값과 최대값을 찾아 차이가 K이하인지 종료조건을 체크해주고, 최소값을 찾은 김에 어항을 돌면서 최소값인 항목에 1을 더해주자.
이제 공중부양시키고 90도 회전하는 부분이 다소 곤란하다. 가장 처음에는 1층의 맨 앞 숫자를 2층으로 올려준다.
first = fishbowl[0].pop(0)
fishbowl.append([first])
그러면 [[1,2,3,4]]와 같이 1층에만 1,2,3,4가 있었던 경우에 [[2,3,4],[1]]로 변했을 것이다.
다음은 불가능할 때 까지 2칸 이상 쌓인 어항을 90도 회전시켜 뒤쪽에 쌓는 작업이다.
while len(fishbowl) <= len(fishbowl[0]) - len(fishbowl[1]):
new_bowl = [list(wow) for wow in zip(*fishbowl)]
new_bowl.reverse()
fishbowl = [fishbowl[0][len(fishbowl[1]):], *new_bowl]
쌓는 것이 불가능한 경우는, 가장 앞쪽에 있는 쌓인 어항의 층수가 너무 높을 때이다. 정확히는, 뒤쪽에 1층으로만 되어있는 부분의 길이보다 크면 안된다.
다음으로, zip(*fishbowl)을 이용하여 공중부양할 부분을 뽑아낸다. 이것이 가능한 이유는 입력받은 argument의 어느 하나라도 iteration이 끝나면 바로 끝나는 zip의 특성 때문이다. 예를 들어 zip([1,2],[3])은 (1,3)만을 yield하고 끝난다.
뽑고 나서 잘 보면, 순서가 뒤집혀있다. [[1,2,3,4],[5,6]]이라면 (1,5)와 (2,6)순으로 뽑아져 나오므로, [[3,4],[2,6],[1,5]]가 되려면 뒤집어주어야 한다(reverse()). 1층에서 공중부양하지 않는 부분을 리스트 슬라이싱하여 앞에다가 포함시켜주면 작업이 끝난다.
여기까지 왔다면 해결한 것이나 다름이 없다. 물고기 수를 조절하고 다시 1층짜리 어항으로 만드는 부분은 두 번 등장하니까 함수로 맨위에 하나 넣어두자. 이 함수를 구현하는 방법은 여러가지가 있겠지만, 나는 어떤 두 숫자사이에서 변화가 일어나는지 수평으로 한번, 수직으로 한번 세어서 변화량을 delta리스트에 기록한 다음 원래 리스트fishbowl에 더해주었다 (move_and_linearize()함수).
마지막 부분은 위에서 만든 함수를 한번 호출하고, 반접고쌓기를 두번 반복하고, 다시한번 호출해준다. 반접고 쌓기 두번은 아래와 같이 간단하게 할 수 있다(파이썬 만세!).
first = fishbowl[0][n // 2:]
second = fishbowl[0][:n // 2][::-1]
fishbowl = [first[n // 4:], second[n // 4:], second[:n // 4][::-1], first[:n // 4][::-1]]
주의할 점
구현하다보면 무엇이 리스트이고 무엇이 수인지 헷갈리므로 잘 구별하자.
Code
링크# https://www.acmicpc.net/problem/23291
from sys import stdin
n, k = map(int, stdin.readline().split())
fishbowl = [list(map(int, stdin.readline().split()))] # save at zeroth floor
# move fish and linearize to zeroth floor
def move_and_linearize(fishbowl):
delta = []
# horizontal
for floor in range(len(fishbowl)):
temp = [0 for _ in range(len(fishbowl[floor]))]
for i in range(len(fishbowl[floor]) - 1):
diff = int((fishbowl[floor][i + 1] - fishbowl[floor][i]) / 5)
temp[i] += diff
temp[i + 1] -= diff
delta.append(temp)
# vertical
for pos in range(len(fishbowl[1])):
for floor in range(len(fishbowl) - 1):
diff = int((fishbowl[floor + 1][pos] - fishbowl[floor][pos]) / 5)
delta[floor][pos] += diff
delta[floor + 1][pos] -= diff
# apply
for floor in range(len(fishbowl)):
for i in range(len(fishbowl[floor])):
fishbowl[floor][i] += delta[floor][i]
new_bowl = []
for wow in zip(*fishbowl):
new_bowl.extend(wow)
new_bowl.extend(fishbowl[0][len(fishbowl[1]):])
return [new_bowl]
for t in range(100000):
# end condition
minimum = min(fishbowl[0])
maximum = max(fishbowl[0])
if maximum - minimum <= k:
print(t)
break
# add fish
for i in range(n):
if fishbowl[0][i] == minimum:
fishbowl[0][i] += 1
# stacking
first = fishbowl[0].pop(0)
fishbowl.append([first])
while True:
if len(fishbowl) <= len(fishbowl[0]) - len(fishbowl[1]):
new_bowl = [list(wow) for wow in zip(*fishbowl)]
new_bowl.reverse()
fishbowl = [fishbowl[0][len(fishbowl[1]):], *new_bowl]
else:
break
fishbowl = move_and_linearize(fishbowl)
# flip half and add to second floor.
first = fishbowl[0][n // 2:]
second = fishbowl[0][:n // 2][::-1]
fishbowl = [first[n // 4:], second[n // 4:], second[:n // 4][::-1], first[:n // 4][::-1]]
fishbowl = move_and_linearize(fishbowl)
여담
이 문제를 마지막으로 삼성 SW 역량 테스트 기출 문제집(이거)를 다 풀었다. 뿌듯하다!
리스트 슬라이싱과 zip을 활용해 문제를 풀었더니 꽤 깔끔하게 구현할 수 있었다. 게다가 별로 푼 사람이 많은 문제는 아니지만 실행시간 1위도 찍어서 만족스럽다.
