[코드트리] 2025 하반기 오전 1번 - 택배 하차

코딩테스트 기출 문제 설명: 택배 하차 | 코드트리

코딩테스트 기출 문제 설명: 택배 하차 | 코드트리

택배 하차 문제

쉽게 푼 건 아니지만 코테 치고 난이도가 낮은 문제였다. 

별다른 알고리즘 없이 차근차근 풀어가면 되는 문제였는데, 여전히 list 순회에서 list out of range는 피해가지 못하고 있음...

N, M = map(int, input().split())
board = [[0 for _ in range(N)] for _ in range(N)]

def print_board(bd):
    for i in range(N):
        for j in range(N):
            print(board[i][j], end=" ")
        print()
    print()

def drop_box(bd, bx):
    k, h, w, c, tmp_row = bx

    # tmp_row에서 어디까지 낮아질 수 있는지 최대 tmp_row 체크
    drop_row = tmp_row
    can_drop = True
    for i in range(tmp_row+h, N):
        for j in range(c, c+w):
            if bd[i][j] != 0:
                can_drop = False
                break
        if can_drop:
            drop_row = i-h+1
        else:
            break

    # bd 값 이동
    for i in range(tmp_row, tmp_row+h):
        for j in range(c, c+w):
            bd[i][j] = 0
    for i in range(drop_row, drop_row+h):
        for j in range(c, c+w):
            bd[i][j] = k

    # bx 값 수정
    return bd, [k, h, w, c, drop_row]

boxes = {}
for i in range(M):
    k, h, w, c = map(int, input().split())
    box = [k, h, w, c-1, 0]

    # 1. 택배 투입
    board, box = drop_box(board, box)

    boxes[k] = box

def left_candidate(bd, bxs):
    # 1 왼쪽으로 이동했을 때 다른 택배와 부딪히지 않고 뺄 수 있는 택배 먼저 하차
    # 2 여러개 이면, 작은 거 먼저 하차
    candidate = []

    i, j = 0, 0
    while True:
        if i >= N:
            break
        for j in range(N):
            # print(i, j)
            if bd[i][j] != 0:
                k, h, w, c, r = bxs[bd[i][j]]
                possible = True
                for m in range(h):
                    if i+m < N and any(bd[i+m][:j]):
                        possible = False
                        # print(f"{i+m}번째 행 체크: {bd[i+m][:j]}")
                    # elif i+m < N:
                        # print(f"{i+m}번째 행은 {bd[i+m]}")
                if possible:
                    candidate.append(k)
                    # print(f"{k} 추가함")
                    # print(k, h, w, c, r)
                    i += (h-1)
                break
        i += 1
    
    # print(candidate)
    candidate.sort()
    
    if candidate:
        return candidate[0]
    return None

def right_candidate(bd, bxs):
    # 1 오른쪽으로 이동했을 때 다른 택배와 부딪히지 않고 뺄 수 있는 택배 먼저 하차
    # 2 여러개 이면, 작은 거 먼저 하차
    candidate = []

    i, j = 0, N-1
    while True:
        if i >= N:
            break
        for j in range(N-1, -1, -1):
            # print(i, j)
            if bd[i][j] != 0:
                k, h, w, c, r = bxs[bd[i][j]]
                possible = True
                for m in range(h):
                    if i+m < N and j+1 < N and any(bd[i+m][j+1:]):
                        possible = False
                if possible:
                    candidate.append(k)
                    i += (h-1)
                break
        i += 1
    
    # print(candidate)
    candidate.sort()
    
    if candidate:
        return candidate[0]
    return None

def delete_candidate(bd, bxs, key):
    k, h, w, c, r = bxs[key]

    for i in range(r, r+h):
        for j in range(c, c+w):
            bd[i][j] = 0
    
    bxs.pop(key)
    
    return bd, bxs

while boxes:
    # print_board(board)
    left = left_candidate(board, boxes)
    if left:
        print(left)
    board, boxes = delete_candidate(board, boxes, left)

    for key in boxes.keys():
        board, box = drop_box(board, boxes[key])
        boxes[key] = box

    # print(left)
    # print_board(board)

    right = right_candidate(board, boxes)
    if right:
        print(right)


    board, boxes = delete_candidate(board, boxes, right)
    for key in boxes.keys():
        board, box = drop_box(board, boxes[key])
        boxes[key] = box

    # print(right)
    # print_board(board)
    # break
    # 2. 택배 하차 (좌측)
        # 1 왼쪽으로 이동했을 때 다른 택배와 부딪히지 않고 뺄 수 있는 택배 먼저 하차
        # 2 여러개 이면, 작은 거 먼저 하차
        # 2 drop 
    # 3. 택배 하차 (우측)