파이썬 알고리즘 풀이: 보스 전투 시뮬레이션으로 패배한 보스 행 제거하기

문제 개요

파이썬으로 간단한 보스 전투 시뮬레이션 문제를 풀어보겠습니다. 0과 1로만 구성된 리스트 fighters와, 여러 개의 이진 리스트로 이루어진 행렬 bosses가 주어진다고 가정해 봅시다.

• fighters 리스트에서 값 1은 전사(fighter)를 의미합니다.
• bosses 행렬의 각 행에서 값 1은 보스(boss)를 의미합니다.
• 전사의 수가 특정 행의 보스 수보다 많으면, 그 행의 보스들은 패배한 것으로 간주되어 제거됩니다.

즉, 최종적으로는 패배하지 않은 보스 행만 남긴 새로운 행렬을 반환해야 합니다.

입력 예시와 동작 원리

예를 들어 다음과 같은 입력이 주어졌다고 합시다.

fighters = [0, 1, 1]
bosses = [
    [0, 0, 0],
    [0, 0, 1],
    [0, 1, 1],
    [1, 1, 1]
]

여기서 전사의 총 수는 2명입니다. 각 보스 행을 하나씩 검사해 보면 다음과 같습니다.

따라서 최종 출력은 다음과 같습니다.

[[0, 1, 1], [1, 1, 1]]

풀이 접근 방법

이 문제는 매우 직관적인 필터링 방식으로 해결할 수 있습니다. 단계별로 정리하면 다음과 같습니다.

1. 전사 수 계산: fighters 리스트의 모든 요소를 합산하여 전사의 총 수(fighter_cnt)를 구합니다.
2. 결과 리스트 초기화: 살아남은 보스 행을 저장할 빈 리스트(result)를 준비합니다.
3. 각 행 검사: bosses의 각 행을 순회하면서, 해당 행의 요소 합계(보스 수)가 전사 수보다 크거나 같으면 그 행을 결과 리스트에 추가합니다.
4. 결과 반환: 필터링이 완료된 결과 리스트를 반환합니다.

핵심 조건은 "전사 수 ≤ 보스 수"일 때 해당 행을 유지하는 것입니다. 전사 수가 보스 수보다 엄격하게 많은 경우에만 그 행이 패배 처리되어 제거됩니다.

구현 코드

class Solution:
    def solve(self, fighters, bosses):
        fighter_cnt = sum(fighters)
        result = []
        for row in bosses:
            if fighter_cnt <= sum(row):
                result.append(row)
        return result

ob = Solution()
fighters = [0, 1, 1]
bosses = [[0, 0, 0], [0, 0, 1], [0, 1, 1], [1, 1, 1]]
print(ob.solve(fighters, bosses))

실행 결과

[[0, 1, 1], [1, 1, 1]]

복잡도 분석

• 시간 복잡도: O(n × m) — n은 bosses 행렬의 행 수, m은 각 행의 길이입니다. 모든 행의 합계를 한 번씩 계산해야 하기 때문입니다.
• 공간 복잡도: O(n) — 결과 리스트에 최대 n개의 행이 저장될 수 있습니다.

마무리

이 문제는 리스트 컴프리헨션을 사용하면 더욱 간결하게 표현할 수도 있습니다. 예를 들어 return [row for row in bosses if sum(fighters) <= sum(row)] 한 줄로 동일한 로직을 구현할 수 있습니다. 전투 시뮬레이션이라는 재미있는 상황 설정 뒤에 숨어 있는 것은 사실 기본적인 조건 필터링 문제라는 점을 기억하면 좋습니다. 이런 유형의 문제는 데이터 전처리나 조건 기반 필터링을 연습하기에 아주 좋은 예제입니다.