[백준][구현] 어항 정리

BAEKJOON Online Judge(BOJ) 문제입니다.

https://www.acmicpc.net/

Baekjoon Online Judge

 

문제

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

23291번: 어항 정리

 

내가 작성한 코드

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

• 강한 구현문제인 만큼 다른 코드들도 복잡함

 

기억해야할 것

• 삼성 코딩테스트 문제
  
  • 단순해보이면서도 복잡한 삼성 코테 문제였음
  • 조건은 단순하다 구현이 어려움
  • 빠진 조건을 꼼꼼히 확인할 것