[PS] 시뮬레이션 실수 정리 (1)

문제: https://www.codetree.ai/ko/frequent-problems/samsung-sw/problems/pirate-captain-coddy/description

처음에 이 문제를 풀 때 min heap 하나만 두고 해결하려고 해봤는데, 안쪽에 있는 배의 우선순위를 높여버릴 때를 대처하기 난감했다. 배들의 정보를 두 벌 가지고 있으면 메모리가 부족할까 싶었는데, 계산을 맡겨보니 생각보다 크지 않았다.

객체 메모리:
• 객체 자체: ~56 bytes
• 속성 4개 (각각 reference): 8 bytes × 4 = 32 bytes
• int 객체 3개: 약 28 bytes × 3 = 84 bytes
• float 객체 1개: 약 24 bytes

👉 합계 ≈ 200 bytes

딕셔너리 메모리:
• key (int): ~28 bytes
• value (reference): 8 bytes
• 해시 테이블 오버헤드 포함해서 보통

👉 엔트리당 ≈ 72 bytes

힙 메모리:
• tuple 객체: ~56 bytes
• 내부 요소 2개 reference: 16 bytes
• int 2개: 28 × 2 = 56 bytes

👉 원소당 ≈ 128 bytes

Ship 20MB (원소 100,000개)
Dict 7MB (원소 100,000개)
Heap 25MB (원소 100,000 * 2, lazy update 고려)

====================
합계 ≈ 52MB -> 절반도 안씀

1차 수정 코드:

import heapq

class Gun:
    def __init__(self, id, p, r):
        self.id = id
        self.p = p # 공격력
        self.r = r # 재장전 시간
        self.last_shoot = 0 # 마지막 발사 시간,  
    
    def __lt__(self, other): #less than
        if self.p == other.p:
            return self.id < other.id
        else:
            return self.p > other.p
    
    def canShoot(self, t):
        if self.last_shoot == 0:
            return True
        elif t >= self.last_shoot + self.r:
            return True
        else:
            return False
    
    def shoot(self, t):
        self.last_shoot = t
    
    def change_power(self, pw):
        self.p = pw
    
    def __str__(self):
        return f"(id: {str(self.id)}, p: {str(self.p)})"

    def __repr__(self):
        return self.__str__()


T = int(input())
guns_dict = {} # Gun 정보 모두 저장
min_heap = []
for t in range(1, T + 1):
    order = list(map(int, input().split()))
    if(order[0] == 100):
        for i in range(order[1]):
            gun = Gun(order[3 * i + 2], order[3 * i + 3], order[3 * i + 4])
            heapq.heappush(min_heap, gun)
            guns_dict[gun.id] = gun
    elif(order[0] == 200):
        gun = Gun(order[1], order[2], order[3])
        heapq.heappush(min_heap, gun)
        guns_dict[gun.id] = gun
    elif(order[0] == 300):
        guns_dict[order[1]].p = order[2] #지연 갱신
        
        
    else:
        # 최대 5개의 valid gun 뽑기
        valid, invalid = [], []
        while(len(min_heap) and len(valid) < 5):
            gun = heapq.heappop(min_heap)
            if(not gun.canShoot(t)): #아직 쿨타임
                invalid.append(gun)
            else:
                # 최신 정보가 2번째 원소보다 크면 사용, 아니면 다시 집어넣기
                if(guns_dict[gun.id].p != gun.p):
                    gun.change_power(guns_dict[gun.id].p)

                if(len(min_heap) == 0 or gun < min_heap[0]):
                    valid.append(gun)
                else:
                    heapq.heappush(min_heap, gun) # 다시 힙에 넣고 되돌아가기

        sum_p = 0
        valid.sort()

        for g in valid:
            sum_p += g.p
            g.shoot(t)
            heapq.heappush(min_heap, g)
            
        for g in invalid:
            heapq.heappush(min_heap, g)

        print(sum_p, len(valid), *[g.id for g in valid])

실수 1.

for i in range(order[1]):
	gun = Gun(order[3 * i + 2], order[3 * i + 3], order[3 * i + 4])
    heapq.heappush(min_heap, gun)
    guns_dict[gun.id] = gun

이 부분에서, 같은 객체를 dict와 heap에 넣는다. 같은 객체를 가리키고 있기 때문에 힙에서 꺼내도 정보가 수정이 된 상태이고 이 비교 로직이 의미가 없다.

if(guns_dict[gun.id].p != gun.p):
	gun.change_power(guns_dict[gun.id].p)

따라서, 객체를 따로 생성해서 삽입이 필요함.
또, 딕셔너리로 Gun 정보 다 가지고 있으니 lt 함수 필요없고 간단히 id랑 power만 튜플로 힙에 저장하는게 좋다.

정답 코드:

import heapq

class Gun:
    def __init__(self, id, p, r):
        self.id = id
        self.p = p # 공격력
        self.r = r # 재장전 시간
        self.last_shoot = 0 # 마지막 발사 시간,  
    
    # def __lt__(self, other): #less than
    #     if self.p == other.p:
    #         return self.id < other.id
    #     else:
    #         return self.p > other.p
    
    def canShoot(self, t):
        if self.last_shoot == 0:
            return True
        elif t >= self.last_shoot + self.r:
            return True
        else:
            return False
    
    def shoot(self, t):
        self.last_shoot = t
    
    def changePower(self, pw):
        self.p = pw
    
    def __str__(self):
        return f"(id: {str(self.id)}, p: {str(self.p)})"

    def __repr__(self):
        return self.__str__()


T = int(input())
guns_dict = {} # Gun 정보 모두 저장
min_heap = []
for t in range(1, T + 1):
    order = list(map(int, input().split()))
    if(order[0] == 100):
        for i in range(order[1]):
            gun = Gun(order[3 * i + 2], order[3 * i + 3], order[3 * i + 4])
            heapq.heappush(min_heap, (-gun.p, gun.id))
            guns_dict[gun.id] = gun
    elif(order[0] == 200):
        gun = Gun(order[1], order[2], order[3])
        heapq.heappush(min_heap, (-gun.p, gun.id))
        guns_dict[gun.id] = gun
    elif(order[0] == 300):
        guns_dict[order[1]].changePower(order[2])
        heapq.heappush(min_heap, (-order[2], order[1]))
        
    else:
        # 최대 5개의 valid gun 뽑기
        valid, invalid = [], []
        while(len(min_heap) and len(valid) < 5):
            gun_tuple = heapq.heappop(min_heap)
            gun = guns_dict[gun_tuple[1]]
            # 최신 정보 갱신
            if(-gun_tuple[0] != gun.p): # 지연 갱신, 정보 다르면 무시
                continue

            if(not gun.canShoot(t)): #아직 쿨타임
                invalid.append(gun_tuple)
            else:
                valid.append(gun_tuple)
                gun.shoot(t)

        sum_p = 0
        valid.sort()

        for g in valid:
            sum_p += -g[0]
            heapq.heappush(min_heap, g)
            
        for g in invalid:
            heapq.heappush(min_heap, g)

        print(sum_p, len(valid), *[g[1] for g in valid])