[99클럽 코테 스터디 23일차 TIL] #힙5

벌써 23일 차네요. 얼마 전에 제 블로그가 몇몇 친구들에게 알려져서 혹시나 친구들이 제 글을 볼까 봐 쪼금 부끄럽네요 :(

그래도 매일매일 보진 않겠죠? 아무튼 열심히 해보겠습니다.

 

문제 설명

---

 

오늘은 무슨 문제냐 하면, 이중벡터로 숫자 배열이 주어지면 각 row에 가장 큰 수를 뽑아 제거를 하는 식으로 진행이 됩니다. 근데 여기서, 제거될 때마다 제거된 수들 중 가장 큰 수를 변수에 따로 더해주어 그 값을 출력하는 문제입니다.

 

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

 

생각 흐름

---

우선, 제가 제일 못 다루고 어려워하는 이중벡터 문제가 나와서 살짝궁 멘붕이 왔었습니다.

요소를 접근해서 다루는 게 어렵다고 해야 하나,, 아무튼 일단 무작정 영어해석먼저 해보았습니다.

 

문제를 이해하는 것은 어렵지 않았습니다. 이중벡터로 된 숫자 grid가 주어지고 이것들의 한 요소인 row에서 가장 큰 수를 각각 제거해 나가는 방식이었습니다.

 

여기서 키포인트는 이러한 수들 중 최댓값을 따로 더해줘서 출력하라는 조건도 있었다는 것이었습니다.

 

저는 고민을 하다가, 우선 이중벡터의 요소인 각 row들의 요소들을 크기순으로 정렬을 해줘야겠다는 생각을 하였습니다.

 

그래서 grid.size() 만큼 반복문을 돌려 grid [i] 들의 vegin()부터 end()까지를 sort() 함수로 오름차순 정렬을 해주었습니다.

 

이렇게 되면 좋은 점은 row들의 가장 마지막 요소가 가장 큰 수가 된다는 점이었고 이를 이용해서 문제를 풀어가 보았습니다.

 

우선, 제거되는 수들의 크기를 비교해야므로 무작정 max라는 변수를 선언해 grid [0]. back()을 max에 입력해 주었고 이를 박복문을 돌려 각 row의 back()들과 일일이 비교해 주며 max에 값을 새로 입력해 주었습니다.

 

그리고 이 값을 answer에 더해주며 문제를 마무리하였습니다.

 

class Solution {
public:
    int deleteGreatestValue(vector<vector<int>>& grid) {
        for (int i = 0; i < grid.size(); i++) { // grid의 요소의 크기대로 반복문을 돌려
            sort(grid[i].begin(), grid[i].end()); // 각 row의 원소들을 오름차순으로 정렬
        }

        int answer = 0; // row에서 제거된 수 중에 큰 수들의 합 (정답)
        while (grid[0].size() > 0) { // grid의 첫번째 요소 수가 0일 될 때까지 (빌 때까지)

            int max = grid[0].back(); // max를 첫번째 마지막 가장 큰 요소로 설정
            for (int i = 0; i < grid.size(); i++) {
                if (grid[i].back() > max) {
                    max = grid[i].back();
                }
            }

            answer += max;

            for (int i = 0; i < grid.size(); i++) {
                grid[i].pop_back();
            }
        }

        return answer;
    }
};

 

 

공부한 내용 정리

---

이번 문제를 풀면서 C++ 이중벡터 요소접근하는 방법을 다시 한번 공부해 봐야겠다는 생각을 하였습니다.

 

그래서 오늘은 이중벡터에 대해 알아보겠습니다.

 

1. 2차원 vector 선언 및 사용

vector은 동적으로 메모리를 할당한 배열입니다.

 

기존 1차원 vector를 값 초기화하여 선언하는 방법은 아래와 같습니다.

vector <데이터타입> 이름 (크기, 초기값);

 

근데 여기서 2차원 벡터를 선언하려면, vector의 데이터 타입에 vector를 또 담는다고 생각하면 됩니다.

 

vector<vector<int>> v;

 

2차원 벡터는 2차원 배열과 같이 대괄호를 이용한 v [i][j]로 각 원소에 접근이 가능합니다.

 

 

 

(1) 행이 m개, 열이 n개인 2차원 벡터를 0으로 초기화하여 선언하는 법

 

vector <vector <int>> v (m, vector <int> (n,0)); 

 

벡터 v는 m개의 원소를 가지고 있으며, 이 m개의 원소들은 각각 n개의 원소를 0으로 초기화한 벡터를 담고 있다는 뜻

 

 

 

int m, n;
cin >> m >> n;

//m*n인 2차원 벡터를 0으로 초기화하여 선언
vector <vector<int>> v(m, vector<int>(n, 0));

for (int i = 0; i < m; i++) {
	for (int j = 0; j < n; j++) {
		cout << v[i][j] << " ";
	}
	cout << "\n";
}

 

 

 

위 방법은 벡터를 선언함과 동시에 메모리도 지정한 만큼 할당했기 때문에, 위와 같은 방법으로 선언한 2차원 벡터는 따로 삽입 연산을 수행할 필요 없이, 범위 (m*n) 내의 원소라면 아무 곳이나 v [i][j]로 접근이 가능합니다.

 

 

(2) 각 행마다 열의 개수가 다를 때, m개의 행만 선언

//벡터를 자료형으로 가지고 있는 m 길이의 벡터 v를 선언
vector<vector<int>> v(m);

v[0].push_back(1);
v[0].push_back(2);
v[0].push_back(3);

v[1].push_back(10);

v[2].push_back(100);
v[2].push_back(200);

v[3].push_back(0);

 

 

 

위와 같이 원하는 행만큼 한 벡터를 선언하고, 각 행마다 삽입 연산 (push, insert)을 통해서 원하는 만큼 데이터를 삽입하는 것도 가능합니다. (각 행마다 다른 원소를 삽입가능)

 

단, 원소를 삽입하기 전에 v [i][j]를 이용하여 원소에 접근할 수 없다, 행 벡터만 선언된 것이고 각 행의 열 벡터는 아무 값도 들어있지 않기 때문입니다.

 

 

2. vector 사용법

Vector의 Iterators

v.begin()	백터 시작점의 주소 값 반환
v.end()	백터 (끝부분 + 1) 주소값 반환
v.rbegin() (revers begin)	백터의 끝 지점을 시작점으로 반환
v.rend() (revers end)	백터의 (시작 + 1) 지점을 끝 부분으로 반환

 

 

Vector Element access(백터의 요소 접근)

v.at(i)	백터의 i번째 요소 접근 (범위 검사함)
v.[i] (operator [])	백터의 i번째 요소 접근 (범위 검사 안함)
v.front()	백터의 첫번째 요소 접근
v.back()	백터의 마지막 요소 접근

 

 

Vector에 요소 삽입

v.push_back()	백터의 마지막 부분에 새로운 요소 추가
v.pop_back()	백터의 마지막 부분 제거
v.insert(삽입할 위치의 주소 값, 변수 값)	사용자가 원하는 위치에 요소 삽입
v.emplace(삽입할 위치의 주소 값, 변수 값)	사용자가 원하는 위치에 요소 삽입(move로 인해 복사생성자 X)
v.emplace_back()	백터의 마지막 부분에 새로운 요소 추가(move로 인해 복사생성자 X)
v.erase(삭제할 위치) or v.erase(시작위치, 끝위치)	사용자가 원하는 index값의 요소를 지운다.
v.clear()	백터의 모든 요소를 지운다.(return size = 0)
v.resize(수정 값)	백터의 사이즈를 조정한다.(범위 초과시 0으로 초기화)
v.swap(백터 변수)	백터와 백터를 스왑한다.

 

Vector Capacity(백터 용량)

v.empty()	백터가 빈공간이면 true, 값이 있다면 false
v.size()	백터의 크기 반환
v.capacity()	heap에 할당된 백터의 실제크기(최대크기) 반환
v.max_size()	백터가 system에서 만들어 질 수 있는 최대 크기 반환
v.reserve(숫자)	백터의 크기 설정
v.shrink_to_fit()	capacity의 크기를 백터의 실제 크기에 맞춤