99클럽 코테 스터디_4기 22일차 TIL

TODAY TIL

안녕하세요 오늘은 grid라는 2차원 배열에서 각 행의 최대 값을 제거하고, 그 값들 중 가장 큰 값을 누적하여 최종 결과를 반환하는 문제를 다루어 보겠습니다. 문제를 단계별로 설명하고, Python 코드와 풀이 과정을 함께 살펴보겠습니다.

문제 설명

주어진 grid는 다음과 같은 2차원 리스트입니다:

grid = [
    [3, 1, 2],
    [5, 4, 6],
    [9, 8, 7]
]

이제 각 반복 단계마다 각 행의 최대 값을 제거한 후, 그 값들 중 가장 큰 값을 누적해 나가는 과정을 반복해야 합니다. grid의 모든 행이 비어 있을 때까지 이 작업을 수행한 후 누적된 값을 반환합니다.

 

풀이 순서

1. answer라는 변수를 초기화하여 결과를 저장합니다.
2. grid[0]이 비어있지 않을 동안 반복문을 실행합니다.
3. 각 행(row)에서 max() 함수를 사용해 가장 큰 값을 찾습니다.
4. 찾은 값을 max_vals 리스트에 추가하고, 해당 값을 해당 행에서 제거합니다.
5. max_vals 리스트에서 가장 큰 값을 찾아 answer에 더합니다.
6. 모든 행이 비어있으면 반복문을 종료하고, 최종 answer를 반환합니다.

코드 설명

다음은 문제를 해결하기 위한 Python 코드입니다

class Solution:
    def deleteGreatestValue(self, grid: List[List[int]]) -> int:
        answer = 0  # 결과를 저장할 변수 초기화
        # grid[0]이 비어있지 않을 동안 반복
        while grid[0]:
            max_vals = []  # 각 행에서 찾은 최대 값을 저장할 리스트
            for row in grid:
                max_val = max(row)  # 각 행에서 최대 값을 찾음
                max_vals.append(max_val)  # 최대 값을 리스트에 추가
                row.remove(max_val)  # 행에서 최대 값을 제거
            answer += max(max_vals)  # 최대 값들 중에서 가장 큰 값을 answer에 더함
        return answer  # 최종 결과 반환

 

단계별 예제

입력 예제

grid가 다음과 같다고 가정합니다:

grid = [
    [3, 1, 2],
    [5, 4, 6],
    [9, 8, 7]
]

 

실행 단계 설명

1. 첫 번째 반복:
   • 각 행에서 최대 값을 찾습니다: [3, 6, 9]
   • 가장 큰 값은 9이며, answer는 9가 됩니다.
   • 업데이트된 grid:
      

grid = [
    [1, 2],
    [4, 5],
    [8, 7]
]

두 번째 반복:

• 각 행에서 최대 값을 찾습니다: [2, 5, 8]
• 가장 큰 값은 8이며, answer는 9 + 8 = 17이 됩니다.
• 업데이트된 grid:
   

grid = [
    [1],
    [4],
    [7]
]

 

세 번째 반복:

• 각 행에서 최대 값을 찾습니다: [1, 4, 7]
• 가장 큰 값은 7이며, answer는 17 + 7 = 24가 됩니다.
• 업데이트된 grid는 비어 있습니다:
   

grid = [
    [],
    [],
    []
]

 

최종 결과

모든 행이 비어 있으므로 반복을 종료하고, answer는 24입니다.

시간 복잡도 분석

• 각 행에서 최대 값을 찾는 작업은 O(n)O(n)O(n)이며, 이를 mmm개의 행에 대해 수행하므로 시간 복잡도는 O(m×n)O(m \times n)O(m×n)입니다.
• m은 행의 수, n은 열의 수입니다.

결론

이 문제는 반복문과 리스트 연산을 활용해 각 행의 최대 값을 계속 제거하면서 누적 합을 구하는 문제입니다. 문제의 핵심은 각 반복마다 각 행의 최대 값을 효율적으로 찾고 제거하는 것입니다.

이 코드와 풀이가 여러분의 이해에 도움이 되었기를 바랍니다. 궁금한 점이나 다른 해석이 있다면 댓글로 남겨주세요!