BAEKJOON Online Judge(BOJ) 문제입니다.
Baekjoon Online Judge
Baekjoon Online Judge 프로그래밍 문제를 풀고 온라인으로 채점받을 수 있는 곳입니다.
www.acmicpc.net
문제
https://www.acmicpc.net/problem/23291
23291번: 어항 정리
마법사 상어는 그동안 배운 마법을 이용해 어항을 정리하려고 한다. 어항은 정육면체 모양이고, 한 변의 길이는 모두 1이다. 상어가 가지고 있는 어항은 N개이고, 가장 처음에 어항은 일렬로 바
www.acmicpc.net
내가 작성한 코드
import sys
from collections import deque
read = sys.stdin.readline
class Node:
def __init__(self, i, v):
self.i = i
self.v = v
def read_data():
N, K = map(int, read().rstrip().split())
fish = []
for i, v in enumerate(list(map(int, read().rstrip().split()))):
fish.append(Node(i, v))
return N, K, fish
def make_first_shape(N, K, fish):
def rotate(n, nq, shape):
nw_shape = []
for _ in range(n):
nw_q = deque()
for i in range(-1, -nq - 1, -1):
nw_q.append(shape[i].popleft())
nw_shape.append(nw_q)
nw_shape.append(shape[-1])
return nw_shape
def make_serial(shape1, n):
nw_q = deque()
for _ in range(n):
for i in range(len(shape1) - 1, -1, -1):
nw_q.append(shape1[i].popleft())
while shape1[-1]:
nw_q.append(shape1[-1].popleft())
return nw_q
shape = [deque(fish)]
n = 1
k = n
while n*2 <= len(shape[-1]):
k = n
shape = rotate(n, n, shape)
if n*2+1 <= len(shape[-1]):
shape = rotate(n, n+1, shape)
k+=1
n += 1
return shape, make_serial([q.copy() for q in shape], k)
def make_second_shape(N, K, shape1):
def rotate(n, nq, shape):
for i in range(-nq, 0):
nw_q = deque()
for _ in range(n):
nw_q.appendleft(shape[i].popleft())
shape.appendleft(nw_q)
def make_serial(shape2):
nw_fish = []
for j in range(N//4):
for i in range(len(shape2)-1, -1, -1):
nw_fish.append(shape2[i][j])
return nw_fish
shape = deque([shape1])
rotate(N//2, 1, shape)
rotate(N//4, 2, shape)
return shape, make_serial(shape)
def add_small(fish):
mn = float('inf')
lst = []
for node in fish:
if node.v < mn:
mn = node.v
lst = [node]
elif node.v == mn:
lst.append(node)
for node in lst:
node.v += 1
def get_gap(fish):
mx = -float('inf')
mn = float('inf')
for node in fish:
if node.v < mn:
mn = node.v
if node.v > mx:
mx = node.v
return mx - mn
def add_injacent(shape):
def add(add_lst, a, b):
d = abs(a.v - b.v) // 5
if d > 0:
if a.v > b.v:
add_lst.append((a, -d))
add_lst.append((b, d))
else:
add_lst.append((a, d))
add_lst.append((b, -d))
add_lst = []
for r in range(len(shape)):
crnt = shape[r]
for c in range(len(crnt)-1):
add(add_lst, crnt[c], crnt[c+1])
if r != len(shape)-1 and c < len(shape[r+1]):
add(add_lst, shape[r][c], shape[r+1][c])
if r != len(shape)-1 and len(crnt) <= len(shape[r+1]):
add(add_lst, crnt[len(crnt)-1], shape[r+1][len(crnt)-1])
for node, d in add_lst:
node.v += d
def get_answer(N, K, fish):
cnt = 0
gap = get_gap(fish)
while gap > K:
shape1, serial_shape1 = make_first_shape(N, K, fish)
shape2, nw_fish = make_second_shape(N, K, serial_shape1)
add_small(fish)
add_injacent(shape1)
add_injacent(shape2)
gap = get_gap(fish)
fish = nw_fish
cnt += 1
return cnt
N, K, fish = read_data()
print(get_answer(N, K, fish))
- 데크
- 값+인덱스를 수시로 바꿔야하기 때문에 매우 복잡함
- 데크를 사용하여 복잡한 인덱스 관리를 조금 편하게 해결
- 객체 사용
- 매 loop마다 배열이 바뀌지 않았다면, 객체를 사용하여 모양을 유지한 채로 빠르게 계산 가능
- 모양을 만든 후 다시 일렬로 만드는 규칙이 따로 있는 줄 몰랐음...
다른 사람이 작성한 코드
None
- 강한 구현문제인 만큼 다른 코드들도 복잡함
기억해야할 것
- 삼성 코딩테스트 문제
- 단순해보이면서도 복잡한 삼성 코테 문제였음
- 조건은 단순하다 구현이 어려움
- 빠진 조건을 꼼꼼히 확인할 것
'코딩테스트' 카테고리의 다른 글
[백준][구현] 온풍기 안녕! (0) | 2022.04.20 |
---|---|
[백준][구현] 마법사 상어와 복제 (0) | 2022.04.20 |
[백준][그리디] 저울 (0) | 2022.04.17 |
[백준][투포인터] 냅색문제 (0) | 2022.04.08 |
[백준][그리디] 보석 도둑 (0) | 2022.04.01 |