99클럽 코테 스터디 29일차 TIL

 

 

오늘의 공부 키워드

2500 Delete Greatest Value in Each Row

 

2500 Delete Greatest Value in Each Row

 

 

이 문제에서 주어진 m x n 행렬 grid는 양의 정수로 이루어져 있습니다. 문제에서 요구하는 연산을 수행하여 grid가 빌 때까지 계속 진행해야 합니다.

주어진 연산은 다음과 같습니다:

1. 각 행에서 가장 큰 값을 삭제합니다. 만약 가장 큰 값이 여러 개 있다면 그 중 하나를 임의로 삭제합니다.
2. 삭제된 원소들 중 최대값을 결과값(answer)에 더합니다.

이 연산을 모든 열이 삭제될 때까지 반복하고, 최종적으로 answer 값을 반환합니다.

해석 예제 1:

입력: grid = [[1,2,4],[3,3,1]] 출력: 8 설명: 각 단계에서 삭제된 값을 보여줍니다.

• 첫 번째 연산에서, 첫 번째 행에서 4를 삭제하고 두 번째 행에서 3을 삭제합니다(3이 두 개 있으며 하나를 임의로 삭제할 수 있습니다). 4를 결과에 추가합니다.
• 두 번째 연산에서, 첫 번째 행에서 2를 삭제하고 두 번째 행에서 3을 삭제합니다. 3을 결과에 추가합니다.
• 세 번째 연산에서, 첫 번째 행에서 1을 삭제하고 두 번째 행에서 1을 삭제합니다. 1을 결과에 추가합니다. 최종 결과 = 4 + 3 + 1 = 8.

해석 예제 2:

입력: grid = [[10]] 출력: 10 설명: 각 단계에서 삭제된 값을 보여줍니다.

• 첫 번째 연산에서, 행에서 10을 삭제합니다. 10을 결과에 추가합니다. 최종 결과 = 10.

풀이 방법:

문제의 요구사항을 따르면 각 행에서 최대값을 찾고, 이 중에서 전체의 최대값을 뽑아 더하는 과정을 반복합니다. m이 행의 수, n이 열의 수이므로, 각 단계마다 O(m) 시간이 걸리며, 최대값을 찾는 것은 O(n)이므로 전체 연산은 O(m * n)의 시간 복잡도를 갖습니다. 각 열을 한 번씩 삭제하므로 총 O(n * m * n)의 연산이 필요합니다. 그러나 이는 최악의 경우이며, 일반적인 파이썬의 내장 함수를 사용하여 최적화할 수 있습니다.

 

파이썬 코드

def max_value_removals(grid):
    answer = 0
    while grid[0]:  # 이 반복은 최대 n번 (열의 수 만큼)
        max_vals = []
        for row in grid:
            max_val = max(row)
            max_vals.append(max_val)
            row.remove(max_val)  # 가장 큰 값 하나를 삭제
        answer += max(max_vals)  # 각 행에서 삭제된 값 중 최대값을 더함
    return answer

# 예제 실행
print(max_value_removals([[1,2,4],[3,3,1]]))  # 출력: 8
print(max_value_removals([[10]]))  # 출력: 10