[코드트리][기출문제] 산타의 선물 공장
자료구조를 제외한 라이브러리 최대한 사용하지 않고 문제풀기 (필요하면 직접 코딩)
문제
문제 풀이 및 회고
class 만들어서 풀어봤다. 시간 초과로 인해 다시 풀었음 (2시간 걸린듯)
코드(python)
시간 초과가 된 코드
출력이 된 부분까지는 답이 다 맞는 것을 확인했었는데 시간초과가 떴다.
from collections import OrderedDict, deque
class Company:
def __init__(self, num):
self.num = num
self.belts = [OrderedDict() for _ in range(self.num+1)] # OrderedDict에 ID가 들어감
self.ID_to_BeltIdx = {} # [ID] = belt_idx
self.ID_to_Weight = {} # [ID] = weight
self.broken_Belt = set() # broken belt인거 넣어줄거임
def get_item_in_belts(self, belt_idx, ID, Weight=None):
self.belts[belt_idx][ID] = 1 # belt 뒤에 상자 추가
self.ID_to_BeltIdx[ID] = belt_idx # ID가 belt를 이동함 ㄹㅇ ㅋㅋ
if Weight != None: # 무게가 적혀있다면 무게 초기화
self.ID_to_Weight[ID] = Weight
return None
def show_info(self):
print("================= SHOW INFO COMPANY =================")
for i in range(1, self.num+1):
print(i ,"th belt : ", self.belts[i])
print("ID_to_BeltIdx : ", self.ID_to_BeltIdx)
print("ID_to_Weight : ", self.ID_to_Weight)
print("broken_Belt : ", self.broken_Belt)
return None
def Rule1(command: list):
"""
m개의 벨트 설치하고 벨트 위에 정확히 n/m개의 물건들을 놓아 총 n개의 물건 준비
각 물건에는 고유한번호 **ID**와 **W**가 적혀있습니다. 번호는 상자마다 다르지만, 무게는 동일한 상자가 있을 수 있습니다.
"""
n, m = command[1], command[2]
COMPANY = Company(m)
for i in range(n):
COMPANY.get_item_in_belts((i//(n//m))+1, command[3+i], command[3+i+n])
return COMPANY
def Rule2(command: list, COMPANY):
"""
원하는 상자의 최대 무게인 w_max가 주어집니다. 1번부터 m번까지 순서대로 벨트를 보며 각 벨트의 맨 앞에 있는 선물 중
무게가 w_max이하라면 하차. 그렇지 않다면 해당 선물을 벨트 맨 뒤로 보냄. 벨트에 있던 상자가 빠지면 한칸씩 앞으로 내려와야함.
내린 상자들 총 무게 출력
"""
w_max = command[1]
total_weight = 0
for ith in range(1, COMPANY.num+1):
if ith in COMPANY.broken_Belt: # 부서진 벨트면 패스
continue
if len(COMPANY.belts[ith]) == 0: # 상자가 없으면 패스
continue
front_box_ID = COMPANY.belts[ith].popitem(last=False)[0]
if COMPANY.ID_to_Weight[front_box_ID] <= w_max: # 무게가 w_max이하라서 하차
total_weight += COMPANY.ID_to_Weight[front_box_ID]
del COMPANY.ID_to_BeltIdx[front_box_ID] # 박스 제거
else: # 해당 선물을 벨트 맨 뒤로 보냄
COMPANY.belts[ith][front_box_ID] = 1
print(total_weight)
return None
def Rule3(command: list, COMPANY):
"""
산타가 제거하기를 원하는 물건의 고유번호 r_id 해당 고유 번호에 해당하는 상자가 놓여있는 벨트가 있다면, 해당 벨트에서 상자를 제거하고
뒤에 있던 상자들은 앞으로 한 칸씩 앞으로 내려옵니다.
r_id가 22인 명령이 주어졌다면 2번째 벨트에 있는 ID 22에 해당하는 상자를 제거하게 됩니다. 그러한 상자가 있는 경우 r_id, 없으면 -1
"""
r_id = command[1]
if r_id not in COMPANY.ID_to_BeltIdx: # 해당 상자가 없음
print(-1)
return None
else: # 해당 상자가 아직 벨트 위에 있는 경우
belt_idx = COMPANY.ID_to_BeltIdx[r_id]
del COMPANY.belts[belt_idx][r_id] # 해당 벨트에서 제거
del COMPANY.ID_to_BeltIdx[r_id] # 전체에서 제거
print(r_id)
return r_id
def Rule4(command: list, COMPANY):
"""
확인하기를 원하는 물건의 고유 번호 f_id. 해당 고유 번호에 해당하는 상자가 놓여있는 벨트가 있다면 벨트 번호 출력. 없다면 -1 출력.
단, 상자가 있는 경우, 해당 상자 위에 있는 모든 상자를 전부 앞으로 가져옵니다. 가져올 시 그 순서는 그대로 유지가 되어야함
"""
f_id = command[1]
if f_id in COMPANY.ID_to_BeltIdx: # 해당 상자가 아직 벨트 위에 있음
belt_num = COMPANY.ID_to_BeltIdx[f_id]
while True: # *** 시간초과가 나는 부분일 것으로 예상됨 => 다른 자료구조 필요
front_item = COMPANY.belts[belt_num].popitem(last=False)[0]
if front_item == f_id:
COMPANY.belts[belt_num][front_item] = 1
COMPANY.belts[belt_num].move_to_end(front_item, last=False) # 해당 상자 맨 앞으로
break
else: # 그 외는 다시 맨 뒤로
COMPANY.belts[belt_num][front_item] = 1
print(belt_num) # 해당 상자가 놓여있는 벨트 출력
else: # 해당 상자가 없음
print(-1)
return None
def Rule5(command: list, COMPANY):
"""
고장 발생한 벨트 번호 b_num. 벨트 고장 발생하면 해당 벨트는 다시 사용할 수 없음.
b_num 벨트의 바로 오른쪽 벨트부터 순서대로 보며 아직 고장나지 않은 벨트 위로 b_num 벨트에 놓여있던 상자들을 아래에서부터 순서대로 하나씩 옮겨줌
b_num 번째 벨트를 제외한 벨트 중 최소 하나 이상이 정상 상태임. (모든 벨트가 망가지는 경우는 없음)
b_num 벨트가 이미 망가져 있다면 -1을. 그렇지 않다면 b_num
"""
b_num = command[1]
if b_num in COMPANY.broken_Belt: # 이미 망가진 벨트
print(-1)
return None
else: # 벨트 망가뜨리기 *** 시간초과가 나는 부분일 것으로 예상됨 => 다른 자료구조 필요
next_b_num = b_num
while True:
next_b_num = (next_b_num)%COMPANY.num + 1 # 다음꺼 탐색
if next_b_num in COMPANY.broken_Belt: # 이미 망가진 벨트
next_b_num += 1 # 다음꺼 탐색
else: # 다음꺼가 멀쩡함
for k, _ in COMPANY.belts[b_num].items(): # 멀쩡한 벨트 위로 슝
COMPANY.belts[next_b_num][k] = 1 # 멀쩡한 벨트 위로
COMPANY.ID_to_BeltIdx[k] = next_b_num # 멀쩡한 벨트 번호로
COMPANY.belts[b_num] = OrderedDict() # b_num 벨트 비우기
COMPANY.broken_Belt.add(b_num) # b_num 벨트가 부서짐
break # 끝
print(b_num) # 정상적으로 고장 처리
return None
if __name__ == "__main__":
q = int(input())
stop = -1
COMPANY = Rule1(list(map(int, input().split())))
#COMPANY.show_info()
for ith_q in range(2, q+1):
command = list(map(int, input().split()))
if command[0] == 200:
Rule2(command, COMPANY)
elif command[0] == 300:
Rule3(command, COMPANY)
elif command[0] == 400:
Rule4(command, COMPANY)
else: # command[0] == 500
Rule5(command, COMPANY)
if stop == ith_q:
print("now ", ith_q, "turn, and command : ", command)
COMPANY.show_info()
break
최적화된 새로운 코드
from collections import OrderedDict, deque
class Box:
def __init__(self, W, belt_idx, front=None, back=None):
self.W = W
self.belt_idx = belt_idx
self.front = front
self.back = back
class Belt:
def __init__(self, head, tail):
self.head = head
self.tail = tail
class Company:
def __init__(self):
self.n = 0
self.m = 0
#self.info_Boxes =
self.Belts = {} # [idx] = Belt
self.broken_Belts = set()
self.Boxes = {} # [ID] = Box
def setting(self, info):
"""
m개의 벨트 설치하고 벨트 위에 정확히 n/m개의 물건들을 놓아 총 n개의 물건 준비
각 물건에는 고유한번호 **ID**와 **W**가 적혀있습니다. 번호는 상자마다 다르지만, 무게는 동일한 상자가 있을 수 있습니다.
"""
self.n, self.m = info[1], info[2]
for idx in range(1, self.m+1): # m개의 벨트에 대해서
head_idx, tail_idx = 3+(self.n//self.m)*(idx-1), 3+(self.n//self.m)*(idx-1) + self.n//self.m-1
head_ID, tail_ID = info[head_idx], info[tail_idx]
self.Belts[idx] = Belt(head_ID, tail_ID) # Belt 초기화
# 벨트 안에 박스들에 대해서
head_W = info[head_idx + self.n] # head 박스 정보
self.Boxes[head_ID] = Box(head_W, idx, None, info[head_idx + 1])
for i in range(1, self.n//self.m-1): # 안에 박스 정보
ID, W = info[head_idx + i], info[head_idx + self.n + i]
self.Boxes[ID] = Box(W, idx, info[head_idx + i -1], info[head_idx + i + 1])
tail_W = info[tail_idx + self.n] # tail 박스 정보
self.Boxes[tail_ID] = Box(tail_W, idx, info[tail_idx -1], None)
def under_weight(self, w_max):
"""
원하는 상자의 최대 무게인 w_max가 주어집니다. 1번부터 m번까지 순서대로 벨트를 보며 각 벨트의 맨 앞에 있는 선물 중
무게가 w_max이하라면 하차. 그렇지 않다면 해당 선물을 벨트 맨 뒤로 보냄. 벨트에 있던 상자가 빠지면 한칸씩 앞으로 내려와야함.
내린 상자들 총 무게 출력
"""
total_weight = 0
for idx in range(1, self.m+1): # m개의 벨트에 대해서
if idx in self.broken_Belts: # 부서진 벨트면 무시
continue
if self.Belts[idx].head == None: # 벨트에 아무것도 없으면 무시
continue
head_box_ID = self.Belts[idx].head
if self.Boxes[head_box_ID].W > w_max: # 무게가 이상이라서 다시 뒤로 올려야함
if self.Belts[idx].head == self.Belts[idx].tail: # Belts에 박스 하나 밖에 없음
continue
else:
next_box_ID = self.Boxes[head_box_ID].back # 2번째 박스
self.Boxes[next_box_ID].front = None # 2번째 박스의 앞은 이제 None
self.Boxes[self.Belts[idx].tail].back = head_box_ID # 꼬리의 뒤는 head_box_ID
self.Boxes[head_box_ID].front = self.Belts[idx].tail # head_box_ID의 front는 idx 벨트의 tail
self.Boxes[head_box_ID].back = None # head_box_ID의 back은 None
self.Belts[idx].head = next_box_ID # idx 벨트의 head는 이제 next_box_ID
self.Belts[idx].tail = head_box_ID # idx 벨트의 tail은 이제 head_box_ID
else: # 이하라면 빼줘야함
total_weight += self.Boxes[head_box_ID].W # 상자 무게 더해주기
if self.Belts[idx].head == self.Belts[idx].tail: # Belts에 박스 하나 밖에 없었음
self.Belts[idx].head = None
self.Belts[idx].tail = None
else: # Belts에 박스 여러개 (2개 이상)
next_box_ID = self.Boxes[head_box_ID].back # 2번째 박스
self.Belts[idx].head = next_box_ID # idx 박스의 head는 2번째 박스
self.Boxes[next_box_ID].front = None # 2번째 박스의 앞은 이제 None
del self.Boxes[head_box_ID] # 박스 전체에서 제거
return total_weight
def remove_box(self, r_id):
"""
산타가 제거하기를 원하는 물건의 고유번호 r_id 해당 고유 번호에 해당하는 상자가 놓여있는 벨트가 있다면, 해당 벨트에서 상자를 제거하고
뒤에 있던 상자들은 앞으로 한 칸씩 앞으로 내려옵니다.
r_id가 22인 명령이 주어졌다면 2번째 벨트에 있는 ID 22에 해당하는 상자를 제거하게 됩니다. 그러한 상자가 있는 경우 r_id, 없으면 -1
"""
if r_id not in self.Boxes: # r_id box가 없음
print(-1)
return None
front_boxID, back_boxID, belt_idx = self.Boxes[r_id].front, self.Boxes[r_id].back, self.Boxes[r_id].belt_idx
if front_boxID == None: # 벨트 맨 앞인 경우
self.Belts[belt_idx].head = back_boxID # back_boxID가 이제 belt_idx에 head임
else:
self.Boxes[front_boxID].back = back_boxID # 사이연결
if back_boxID == None: # 벨트 맨 뒤인 경우
self.Belts[belt_idx].tail = front_boxID
else:
self.Boxes[back_boxID].front = front_boxID # 사이 연결
del self.Boxes[r_id] # 전체 박스에서 r_id 삭제
print(r_id)
return None
def find_box(self, f_id):
"""
확인하기를 원하는 물건의 고유 번호 f_id. 해당 고유 번호에 해당하는 상자가 놓여있는 벨트가 있다면 벨트 번호 출력. 없다면 -1 출력.
단, 상자가 있는 경우, 해당 상자 위에 있는 모든 상자를 전부 앞으로 가져옵니다. 가져올 시 그 순서는 그대로 유지가 되어야함
"""
if f_id not in self.Boxes: # r_id box가 없음
print(-1)
return None
front_boxID, back_boxID, belt_idx = self.Boxes[f_id].front, self.Boxes[f_id].back, self.Boxes[f_id].belt_idx
if self.Belts[belt_idx].head == self.Belts[belt_idx].tail: # belt_idx에 박스가 하나
pass # 실행할 것 없음
elif self.Belts[belt_idx].head == f_id: # f_id가 belt의 맨 앞임
pass # 실행할 것 없음
else:
head_boxID, tail_boxID = self.Belts[belt_idx].head, self.Belts[belt_idx].tail # belt_idx의 head, tail
self.Boxes[head_boxID].front = tail_boxID # head는 tail에 붙여짐
self.Boxes[tail_boxID].back = head_boxID # tail에 head가 붙여짐
self.Boxes[front_boxID].back = None # f_id의 앞 상자(front_box_ID)는 tail로 가게 됨
self.Belts[belt_idx].tail = front_boxID # f_id의 앞 상자(front_box_ID)가 belt_idx tail로
self.Belts[belt_idx].head = f_id # f_id를 가장 앞으로 두기
self.Boxes[f_id].front = None # f_id의 맨 앞은 None
print(belt_idx)
return None
def break_belt(self, b_num):
"""
고장 발생한 벨트 번호 b_num. 벨트 고장 발생하면 해당 벨트는 다시 사용할 수 없음.
b_num 벨트의 바로 오른쪽 벨트부터 순서대로 보며 아직 고장나지 않은 벨트 위로 b_num 벨트에 놓여있던 상자들을 아래에서부터 순서대로 하나씩 옮겨줌
b_num 번째 벨트를 제외한 벨트 중 최소 하나 이상이 정상 상태임. (모든 벨트가 망가지는 경우는 없음)
b_num 벨트가 이미 망가져 있다면 -1을. 그렇지 않다면 b_num
"""
if b_num in self.broken_Belts: # 벨트가 이미 망가져있음
print(-1)
return None
if self.Belts[b_num] == None: # 벨트에 아무것도 없음
self.broken_Belts.add(b_num) # b_num 벨트 부시기
print(b_num)
return None
next_belt_idx = b_num # 옮길 벨트 idx
while True:
next_belt_idx = (next_belt_idx)%self.m + 1
if next_belt_idx not in self.broken_Belts:
break
next_tailID = self.Belts[next_belt_idx].tail # b_num에서 -> next 벨트로 옮길 거임
bnum_headID = self.Belts[b_num].head
self.Boxes[next_tailID].back = bnum_headID # next의 tail에 b_num head
self.Boxes[bnum_headID].front = next_tailID # b_num head에 next tail
self.Belts[next_belt_idx].tail = self.Belts[b_num].tail # 꼬리 붙이기
bnum_boxes_idx = bnum_headID
while True:
self.Boxes[bnum_boxes_idx].belt_idx = next_belt_idx
bnum_boxes_idx = self.Boxes[bnum_boxes_idx].back
if bnum_boxes_idx == None: # 원소 다 옮겼음
break
self.Belts[b_num].head, self.Belts[b_num].tail = None, None # b_num 비우기
self.broken_Belts.add(b_num) # b_num 벨트 부시기
print(b_num)
return None
def show_info(self):
print("================= SHOW INFO COMPANY =================")
for i in range(1, self.m+1):
print(i ,"th belt(head, tail) : ", self.Belts[i].head, self.Belts[i].tail)
print("Boxes : ",)
for k, v in self.Boxes.items():
print("ID, W, belt_idx, front, back : ", k, v.W, v.belt_idx, v.front, v.back)
#print("ID_to_BeltIdx : ", self.ID_to_BeltIdx)
#print("ID_to_Weight : ", self.ID_to_Weight)
print("broken_Belt : ", self.broken_Belts)
return None
def establish_company(command: list):
"""
m개의 벨트 설치하고 벨트 위에 정확히 n/m개의 물건들을 놓아 총 n개의 물건 준비
각 물건에는 고유한번호 **ID**와 **W**가 적혀있습니다. 번호는 상자마다 다르지만, 무게는 동일한 상자가 있을 수 있습니다.
"""
n, m = command[1], command[2]
COMPANY = Company()
COMPANY.setting(command)
return COMPANY
def unload_item(command: list, COMPANY):
"""
원하는 상자의 최대 무게인 w_max가 주어집니다. 1번부터 m번까지 순서대로 벨트를 보며 각 벨트의 맨 앞에 있는 선물 중
무게가 w_max이하라면 하차. 그렇지 않다면 해당 선물을 벨트 맨 뒤로 보냄. 벨트에 있던 상자가 빠지면 한칸씩 앞으로 내려와야함.
내린 상자들 총 무게 출력
"""
w_max = command[1]
total_weight = COMPANY.under_weight(w_max)
print(total_weight)
return None
def remove_item(command: list, COMPANY):
"""
산타가 제거하기를 원하는 물건의 고유번호 r_id 해당 고유 번호에 해당하는 상자가 놓여있는 벨트가 있다면, 해당 벨트에서 상자를 제거하고
뒤에 있던 상자들은 앞으로 한 칸씩 앞으로 내려옵니다.
r_id가 22인 명령이 주어졌다면 2번째 벨트에 있는 ID 22에 해당하는 상자를 제거하게 됩니다. 그러한 상자가 있는 경우 r_id, 없으면 -1
"""
r_id = command[1]
COMPANY.remove_box(r_id)
return None
def find_item(command: list, COMPANY):
"""
확인하기를 원하는 물건의 고유 번호 f_id. 해당 고유 번호에 해당하는 상자가 놓여있는 벨트가 있다면 벨트 번호 출력. 없다면 -1 출력.
단, 상자가 있는 경우, 해당 상자 위에 있는 모든 상자를 전부 앞으로 가져옵니다. 가져올 시 그 순서는 그대로 유지가 되어야함
"""
f_id = command[1]
COMPANY.find_box(f_id)
return None
def break_belt(command: list, COMPANY):
"""
고장 발생한 벨트 번호 b_num. 벨트 고장 발생하면 해당 벨트는 다시 사용할 수 없음.
b_num 벨트의 바로 오른쪽 벨트부터 순서대로 보며 아직 고장나지 않은 벨트 위로 b_num 벨트에 놓여있던 상자들을 아래에서부터 순서대로 하나씩 옮겨줌
b_num 번째 벨트를 제외한 벨트 중 최소 하나 이상이 정상 상태임. (모든 벨트가 망가지는 경우는 없음)
b_num 벨트가 이미 망가져 있다면 -1을. 그렇지 않다면 b_num
"""
b_num = command[1]
COMPANY.break_belt(b_num)
return None
if __name__ == "__main__":
q = int(input())
stop = -1
COMPANY = establish_company(list(map(int, input().split())))
#COMPANY.show_info()
for ith_q in range(2, q+1):
command = list(map(int, input().split()))
if command[0] == 0:
print("now ended!!!")
COMPANY.show_info()
break
if command[0] == 200:
unload_item(command, COMPANY)
elif command[0] == 300:
remove_item(command, COMPANY)
elif command[0] == 400:
find_item(command, COMPANY)
else: # command[0] == 500
break_belt(command, COMPANY)
if stop == ith_q:
print("now ", ith_q, "turn, and command : ", command)
COMPANY.show_info()
break
훨씬 더 빠른 풀이
def Santa():
Q = int(input())
order = list(map(int, input().strip().split(' ')))
N, M = order[1] // order[2], order[2]
break_belt = [False for _ in range(M)]
# 1. 공장 설립
eigen, link, reverse_link, head = {}, [{} for _ in range(M)], [{} for _ in range(M)], [0 for _ in range(M)]
for idx_1 in range(M):
for idx_2 in range(N):
eigen[order[3 + idx_1 * N + idx_2]] = order[3 + order[1] + idx_1 * N + idx_2]
if idx_2 != N - 1:
link[idx_1][order[3 + idx_1 * N + idx_2]] = order[3 + idx_1 * N + idx_2 + 1]
reverse_link[idx_1][order[3 + idx_1 * N + idx_2 + 1]] = order[3 + idx_1 * N + idx_2]
else:
link[idx_1][order[3 + idx_1 * N + idx_2]] = order[3 + idx_1 * N]
reverse_link[idx_1][order[3 + idx_1 * N]] = order[3 + idx_1 * N + idx_2]
head[idx_1] = order[3 + idx_1 * N]
for _ in range(Q - 1):
order_num, value = map(int, input().strip().split(' '))
# 2. 물건 하차
if order_num == 200:
weight_sum = 0
for idx_1 in range(M):
if len(link[idx_1]):
if eigen[head[idx_1]] <= value:
weight_sum += eigen[head[idx_1]]
pre, nex = reverse_link[idx_1][head[idx_1]], link[idx_1][head[idx_1]]
del link[idx_1][head[idx_1]]
del reverse_link[idx_1][head[idx_1]]
if len(link[idx_1]):
link[idx_1][pre] = nex
reverse_link[idx_1][nex] = pre
head[idx_1] = nex
else:
head[idx_1] = 0
else:
head[idx_1] = link[idx_1][head[idx_1]]
print(weight_sum)
# 3. 물건 제거
if order_num == 300:
breaker = False
for idx_1 in range(M):
if link[idx_1].get(value, 0):
pre, nex = reverse_link[idx_1][value], link[idx_1][value]
del link[idx_1][value]
del reverse_link[idx_1][value]
print(value)
if len(link[idx_1]):
link[idx_1][pre] = nex
reverse_link[idx_1][nex] = pre
if head[idx_1] == value:
head[idx_1] = nex
else:
head[idx_1] = 0
breaker = True
break
if not breaker:
print(-1)
# 4. 물건 확인
if order_num == 400:
breaker = False
for idx_1 in range(M):
if link[idx_1].get(value, 0):
print(idx_1 + 1)
head[idx_1] = value
breaker = True
break
if not breaker:
print(-1)
# 5. 벨트 고장
if order_num == 500:
break_idx = value - 1
if break_belt[break_idx]:
print(-1)
else:
move_idx = break_idx
break_belt[break_idx] = True
print(break_idx + 1)
if len(link[break_idx]):
while True:
move_idx = (move_idx + 1) % M
if not break_belt[move_idx]:
move_front, move_back = head[move_idx], reverse_link[move_idx][head[move_idx]]
break_front, break_back = head[break_idx], reverse_link[break_idx][head[break_idx]]
for key in link[break_idx]:
if key == break_front:
reverse_link[move_idx][key] = move_back
link[move_idx][key] = link[break_idx][key]
elif key == break_back:
link[move_idx][key] = move_front
reverse_link[move_idx][key] = reverse_link[break_idx][key]
else:
link[move_idx][key] = link[break_idx][key]
reverse_link[move_idx][key] = reverse_link[break_idx][key]
link[move_idx][move_back] = break_front
reverse_link[move_idx][move_front] = break_back
head[break_idx] = 0
link[break_idx], reverse_link[break_idx] = {}, {}
break
Santa()
댓글남기기