99클럽 코테 스터디 23일차 TIL + 이차원 벡터(C++)

문제

[리트코드] Delete Greatest Value in Each Row

https://leetcode.com/problems/delete-greatest-value-in-each-row/description/

 

문제 해석

(번역: 챗지피티)

 

m x n 크기의 양의 정수로 구성된 행렬 grid가 주어집니다.

아래의 연산을 행렬이 비어질 때까지 반복 수행합니다:

1. 각 행(row)에서 가장 큰 값을 삭제합니다.
   • 만약 같은 값이 여러 개 있다면, 그중 아무 값이나 삭제합니다.
2. 삭제된 값들 중 최댓값을 구해, 그 값을 answer에 더합니다.
3. 각 반복이 끝날 때마다 열(column)의 개수가 1씩 감소합니다.

연산을 모두 수행한 후, answer의 최종 값을 반환하면 됩니다.

 

예제1

입력: grid = [[1, 2, 4], [3, 3, 1]]

출력: 8

설명: 위 그림은 각 단계에서 제거된 값을 보여줍니다.

1. 첫 번째 연산:
   • 첫 번째 행에서 4를 제거하고, 두 번째 행에서 3을 제거합니다.
   • (참고로, 두 번째 행에 3이 두 개 있으므로 둘 중 아무 값을 제거해도 됩니다.)
   • answer에 4를 더합니다.
2. 두 번째 연산:
   • 첫 번째 행에서 2를 제거하고, 두 번째 행에서 3을 제거합니다.
   • answer에 3을 더합니다.
3. 세 번째 연산:
   • 첫 번째 행에서 1을 제거하고, 두 번째 행에서 1을 제거합니다.
   • answer에 1을 더합니다.

최종 결과: answer = 4 + 3 + 1 = 8

 

코드

class Solution {
public:
    int deleteGreatestValue(vector<vector<int>>& grid) {
        int answer = 0;

        // 이차원 벡터의 열의 수가 0보다 클 때까지 반복
        while (grid[0].size() > 0) {
            int max_value = 0; // 전체 행에서의 최댓값

            // 이차원 벡터의 행의 수만큼 반복
            for (int i = 0; i < grid.size(); i++) {
                // 해당 행의 최댓값의 인덱스
                int max_idx = max_element(grid[i].begin(), grid[i].end()) - grid[i].begin();
                // 해당 행의 최댓값
                int max_tmp = *max_element(grid[i].begin(), grid[i].end());
                // 전체 행에서의 최댓값 갱신
                max_value = max(max_value, max_tmp);
                // 해당 행에서의 최댓값을 삭제
                grid[i].erase(grid[i].begin() + max_idx);
            }
            
            answer += max_value; // 최댓값을 누적
        }

        return answer;
    }
};

 

풀이

이차원 벡터의 열의 수가 0보다 클 때까지 반복을 도는데, 행의 수만큼 내부 반복문을 돌면서

각 행에서의 최댓값을 찾아 행에서 삭제하고,

삭제된 값들 중 최댓값을 누적하여 반환한다.

 

✅ 핵심 C++ 문법

1. 이차원 벡터(배열)의 열의 수: grid[0].size()
2. 이차원 벡터(배열)의 행의 수: grid.size()
3. 이차원 벡터의 한 행에서의 최댓값의 인덱스: max_element(grid[i].begin(), grid[i].end()) - grid[i].begin();
4. 이차원 벡터의 한 행에서의 최댓값: *max_element(grid[i].begin(), grid[i].end());
5. 이차원 벡터에서 i행 j열 원소를 제거: grid[i].erase(grid[i].begin() + j);

 

회고

이차원 배열의 행, 열 수를 구하는 것부터 헷갈려서 아직 기본이 많이 부족하구나 싶었다.

쉬운 문제라고 지나치지 않아야 하는 이유…