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

https://www.codetree.ai/ko/frequent-problems/samsung-sw/problems/delivery-service/description

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

 

이런 극한 시뮬레이션 문제들은 항상 한 번에 안 풀리고, 두세번 검토를 해야지 풀리네요ㅜ

 

이 문제에서는 크게 2가지가 어려웠습니다.

1. 박스 정보를 어떻게 저장할 것인가

2. 왼쪽, 오른쪽 빼줄 때 

 

오히려 박스 개체를 중력 적용하는건 그리 어렵지 않았습니다..

 

1. 박스 정보 저장하는 법.

다른 풀이에서는 클래스나 구조체를 만들어 풀었는데, 저는 그냥 리스트에 냅다 다 때려박았습니다.

position이라는 리스트에

[a. 박스의 좌상단 b. 박스의 좌하단 c. 순위 d. 번호]

이런 식으로요 ㅋㅋ

 

여기서 c. 순위 때문에 고생 좀 했습니다. 리스트나 자료구조를 더 쓰지 않고 풀고싶었습니다..

박스를 뺀 후에 다시 중력을 적용할 때 바닥에 가까운 박스부터 차례로 적용해야 하기 때문에

'순위' 개념을 도입했습니다. 바닥과 가까울 수록 높은 순위를 주었습니다.

처음에는 좀 무식한 방법이라 생각했는데.. 여전히 좀 무식한 것 같습니다ㅜ

 

1번이 해결되면 자연스레 2번도 가능합니다.

2. 왼쪽, 오른쪽 빼주기

이건 모든 박스에 대해, 좌 또는 우 방향에 걸리는 박스가 있는지 검사해준다음 k값(번호)이 가장 작은 것 골라주면 됩니다.

 

박스의 좌상단, 좌하단을 구해서 저장해두었더니 여러모로 요긴하게 써먹었습니다.

다만 아쉬운건, 하차한 박스 개체는 아예 삭제하는게 나았을 듯 합니다. O(N)정도면....
그리고 코드 정리가 필요해보이네요

N,M = map(int, input().split())

# 택배번호k, 세로h, 가로w, 좌측좌표c
delivery = []
for _ in range(M):
    k,h,w,c = map(int, input().split())
    c -= 1
    delivery.append([k,h,w,c])

arr = [[0]*N for _ in range(N)]
position = [] 

def gravity(position):
    #print(position)

    order = sorted(position,key=lambda x : -x[2])
    for i in range(M):
        topleft,bottomright,s,k = order[i]
        if k != -1:
            #print(pos)
            stop = False

            new_pos = N
            for j in range(bottomright[0]+1,N): # 행을 증가 시킴
                for l in range(topleft[1], bottomright[1]+1): # 너비를 검사하면서 닿는게 있으면 stop
                    if arr[j][l] != 0:
                        new_pos = j
                        stop = True
                        break
                if stop:
                    break
            # 원래 값 삭제
            w = bottomright[1] - topleft[1] + 1
            h = bottomright[0]-topleft[0]+1
            c = topleft[1]

            for r in range(topleft[0],bottomright[0]+1): # 1,3
                arr[r][c:c+w] = [0]*w

            # 위치 기록
            for r in range(new_pos-h,new_pos): # 4-2, 4
                arr[r][c:c+w] = [k]*w

            order[i] = [(new_pos-h,c),(new_pos-1,c+w-1),s,k]
    return order

# 택배 투입
for i in range(M):
    k,h,w,c = delivery[i] # 8 2 4 1->0
    for r in range(0,h):
        arr[r][c:c+w] = [k]*w
    # 중력
    stop = False
    pos = N
    for j in range(h,N): # 행을 증가 시킴
        for l in range(c, c+w): # 너비를 검사하면서 닿는게 있으면 stop
            if arr[j][l] != 0:
                pos = j
                stop = True
                break
        if stop:
            break

    for r in range(0,h):
        arr[r][c:c+w] = [0]*w

    # 위치 기록
    for r in range(pos-h,pos):
        arr[r][c:c+w] = [k]*w

    for s in range(N):
        if pos-1 == s:
            position.append([(pos-h,c),(pos-1,c+w-1),s, k]) # s==5 바닥, s==0 꼭대기

answer = []
while True:
    clear = False
    # 택배 하차 (좌측))
    candidate = 1e+9
    for i in range(len(position)):
        topleft, bottomright, s,k = position[i]
        if k!=-1:
            ok = True
            # 이 택배가 차지하는 각 행 r에 대해,
            for r in range(topleft[0], bottomright[0]+1):
                # 왼쪽에 다른 택배가 있는지 확인
                for c in range(0, topleft[1]):
                    if arr[r][c] != 0:   # 다른 택배/장애물이 있음
                        ok = False
                        break
                if not ok:
                    break
            if ok:
                if candidate > k:
                    candidate = k
                    del_idx = i

    if candidate != 1e+9:
        answer.append(candidate)

        for i in range(N):
            for j in range(N):
                if arr[i][j] == candidate:
                    arr[i][j] = 0
        position[del_idx] = [(-1,-1),(-1,-1),-1,-1]
    else:
        clear = True   # 더 이상 뺄 수 있는 택배 없음

    # 중력 다시
    position = gravity(position)

    # 택배 하차 우측
    candidate = 1e+9

    for i in range(len(position)):
        topleft, bottomright, s,k = position[i]
        if k!=-1:
            ok = True
            # 이 택배가 차지하는 각 행 r에 대해,
            for r in range(topleft[0], bottomright[0]+1):
                # 오른쪽에 다른 택배가 있는지 확인
                for c in range(bottomright[1]+1,N):
                    if arr[r][c] != 0:   # 다른 택배/장애물이 있음
                        ok = False
                        break
                if not ok:
                    break
            if ok:
                if candidate > k:
                    candidate = k
                    del_idx = i

    if candidate != 1e+9:
        answer.append(candidate)

        for i in range(N):
            for j in range(N):
                if arr[i][j] == candidate:
                    arr[i][j] = 0
        position[del_idx] = [(-1,-1),(-1,-1),-1,-1]
    else:
        clear = True   # 더 이상 뺄 수 있는 택배 없음
    
    # 중력 다시
    position = gravity(position)

    # 종료 조건
    if clear:
        break
for ans in answer:
    print(ans)