[프로그래머스] 붕대 감기, 석유 시추 - Python

문제 - [PCCP 기출문제] 1번

프로그래머스 붕대 감기

풀이

# t초 동안 붕대를 감으면서 1초마다 x만큼의 체력을 회복
# t초 연속으로 붕대를 감는데 성공한다면 y만큼의 체력을 추가 회복

# 몬스터에게 공격당해 기술이 취소당하거나 기술이 끝나면 그 즉시 붕대 감기 다시 사용, 연속 성공 시간 0 초기화

# 현재 체력이 0이하가 되면 캐릭터가 죽으며 더 이상 체력을 회복할 수 없음!

# 붕대감기 기술의 정보[시전 시간, 초당 회복량, 추가 회복량], 캐릭터가 가진 최대 체력,
# 몬스터 공격 패턴[공격 시간, 피해량]
def solution(bandage, health, attacks):
    max_health = health
    last_time = attacks[-1][0] + 1
    attack_time = []
    success_cnt = 0

    for attack in attacks:
        attack_time.append(attack[0])

    for i in range(1, last_time):
        # 죽으면 게임 끝
        if health <= 0:
            break

        # 공격
        if i in attack_time:
            success_cnt = 0
            health -= attacks[attack_time.index(i)][1]
        else:
            # 공격받지 않는다면
            if health < max_health:
                health += bandage[1]
                if health > max_health:
                    health = max_health
            success_cnt += 1

        if success_cnt == bandage[0]:
            if health < max_health:
                health += bandage[2]
                if health > max_health:
                    health = max_health
            success_cnt = 0

    # 캐릭터가 끝까지 생존할 수 있는지 구해라(남은 체력 or -1 반환)
    return health if health > 0 else -1

첫 번째 풀이에서 6, 9번 테스트 케이스만 실패했는데 문제를 다시 자세히 읽어보고

이때, 현재 체력이 0 이하가 되면 캐릭터가 죽으며 더 이상 체력을 회복할 수 없습니다.
-> 체력이 0이하가 되면 종료 -> 죽고나서 회복되지 않게 처리

이 부분을 추가해 맞출 수 있었다.

개선 코드

def solution(bandage, health, attacks):
    max_health = health
    last_time = attacks[-1][0] + 1
    attack_time_set = set()
    success_cnt = 0

    for attack in attacks:
        attack_time_set.add(attack[0])

    attack_dict = {attack[0]: attack[1] for attack in attacks}

    for i in range(1, last_time):
        # 죽으면 게임 끝
        if health <= 0:
            break

        # 공격
        if i in attack_time_set:
            success_cnt = 0
            health -= attack_dict[i]
        else:
            # 공격받지 않는다면
            if health < max_health:
                health += bandage[1]
                if health > max_health:
                    health = max_health
            success_cnt += 1

        if success_cnt == bandage[0]:
            if health < max_health:
                health += bandage[2]
                if health > max_health:
                    health = max_health
            success_cnt = 0

    # 캐릭터가 끝까지 생존할 수 있는지 구해라(남은 체력 or -1 반환)
    return health if health > 0 else -1

attack_time을 집합으로 사용하고 attack_dict를 만들어 사용하면 공격 시간을 확인하는 시간을 줄일 수 있다. (집합을 사용하는 in 연산자는 평균적으로 O(1) 시간이 걸린다)

⏰ 시간복잡도 O(n + T)
n: 공격 시간, T: last_time(최대 공격 시간)

문제 - [PCCP 기출문제] 2번

프로그래머스 석유 시추

풀이

# 세로 n, 가로 m
# 시추관을 수직(열)으로 단 하나만 뚫을때, 가장 많은 석유를 뽑을 수 있는 시추관의 위치를 찾아라
# 상, 하, 좌, 우로 연결된 석유는 하나의 덩어리

from collections import deque

def solution(land):
    n = len(land) # 세로
    m = len(land[0]) # 가로
    visited = [[0 for _ in range(m)] for _ in range(n)]

     # 각 열마다 최대 석유 덩어리 크기를 저장할 배열
    max_oil_in_column = [0] * m

    # 상하좌우
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    def bfs(i, j):
        queue = deque()
        queue.append((i, j))
        visited[i][j] = 1
        cnt = 1 # 석유 덩어리의 크기
        min_y, max_y = j, j

        while queue:
            x, y = queue.popleft()
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]

                if 0 <= nx < n and 0 <= ny < m and land[nx][ny] == 1 and not visited[nx][ny]:
                    visited[nx][ny] = 1
                    queue.append((nx, ny))
                    cnt += 1
                    min_y = min(min_y, ny) # 열에서 가장 작은
                    max_y = max(max_y, ny) # 열에서 가장 큰

        # 최소, 최대 열 인덱스에 석유 덩어리의 크기 업데이트
        for y in range(min_y, max_y + 1):
                max_oil_in_column[y] += cnt



    # 탐색
    for i in range(n):
        for j in range(m):
            if land[i][j] == 1 and not visited[i][j]:
                bfs(i, j)

    # 가장 큰 석유 덩어리를 포함하는 열의 크기 반환
    return max(max_oil_in_column)

bfs 탐색은 돌 수 있지만 누적한 값을 탐색 마지막에 저장하는 방법이 아닌 해당 석유 덩어리 칸마다 모두 해당 석유 덩어리 크기(탐색 완료 크기)로 업데이트하는 부분과
수직(열 인덱스)마다 최대 열을 찾아주는 부분을 모르겠어서 다른 풀이를 참고했다.

해당 부분은 bfs 탐색의 최소, 최대 열을 찾고, '각 열마다 최대 석유 덩어리 크기를 저장할 배열'에 해당 범위에 해당하는 열에 현재 석유 덩어리의 크기를 더해주면 된다.
마지막에 그 중 가장 큰 크기를 반환하면 수직으로 석유를 뽑았을때 가장 많은 석유를 뽑는 값을 알 수 있다.

⏰ 시간복잡도 O(n * m)