문제
거대한 경기장의 좌석 배치표는 대부분 비어 있어서, 모든 칸을 저장하면 메모리가 낭비됩니다. SparseGrid는 0이 아닌 값이 들어 있는 칸만 저장하고, 나머지 칸은 모두 0으로 봅니다. 격자는 rows개의 행과 cols개의 열로 시작하며, 처음에는 저장된 칸이 없습니다. 다음 연산을 차례대로 처리하세요.
set r c v: (r, c) 칸의 값을v로 바꿉니다. 0으로 바꾸면 그 칸은 저장소에서 지웁니다.get r c: (r, c) 칸의 값을 출력합니다.count: 0이 아닌 칸의 개수를 출력합니다.row_sum r:r행 값들의 합을 출력합니다.width: 현재 열의 개수를 출력합니다.remove_col c:c열을 삭제합니다. 그 열의 칸은 사라지고, 오른쪽에 있던 칸은 모두 한 열씩 왼쪽으로 옮겨지며, 격자의 열이 하나 줄어듭니다.
행과 열은 0부터 번호를 매기며, 모든 인덱스는 연산 시점의 격자 안에 있습니다.
sparse_grid(rows, cols, operations) 함수를 구현하세요.
입력
rows: 행의 개수입니다.
cols: 처음 열의 개수입니다.
operations: 차례대로 처리할 연산들입니다.
출력
get, count, row_sum, width의 출력을 발생한 순서대로 반환하세요.
제약 조건
1 ≤ rows ≤ 1,000,000
1 ≤ cols ≤ 1,000,000
0 ≤ 연산의 개수 ≤ 1,000
−1,000,000 ≤ v ≤ 1,000,000
예시
입력:
rows = 3
cols = 4
operations = ["set 0 1 5", "set 0 3 2", "set 2 2 7", "row_sum 0", "count", "get 1 1"]
예상 출력:
expected = [7, 3, 0]
입력:
long long rows = 3;
long long cols = 4;
std::vector<std::string> operations = {"set 0 1 5", "set 0 3 2", "set 2 2 7", "row_sum 0", "count", "get 1 1"};
예상 출력:
std::vector<long long> expected = {7, 3, 0};
입력:
long rows = 3;
long cols = 4;
string[] operations = new string[] {"set 0 1 5", "set 0 3 2", "set 2 2 7", "row_sum 0", "count", "get 1 1"};
예상 출력:
long[] expected = new long[] {7, 3, 0};
설명
0행에는 5와 2가 있으므로 합은 7입니다. 저장된 칸은 세 개이고, (1, 1)은 한 번도 값을 넣지 않았으므로 0입니다.
입력:
rows = 2
cols = 3
operations = ["set 1 0 4", "set 1 2 9", "remove_col 0", "get 1 1", "width", "count"]
예상 출력:
expected = [9, 2, 1]
입력:
long long rows = 2;
long long cols = 3;
std::vector<std::string> operations = {"set 1 0 4", "set 1 2 9", "remove_col 0", "get 1 1", "width", "count"};
예상 출력:
std::vector<long long> expected = {9, 2, 1};
입력:
long rows = 2;
long cols = 3;
string[] operations = new string[] {"set 1 0 4", "set 1 2 9", "remove_col 0", "get 1 1", "width", "count"};
예상 출력:
long[] expected = new long[] {9, 2, 1};
설명
0열을 삭제하면 4가 사라지고 2열의 9가 1열로 옮겨지므로 get 1 1은 9, 열 수는 2, 남은 칸은 하나입니다.
접근 방법
먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.
힌트 1
(행, 열)을 값에 대응시키는 맵이 잘 맞습니다. 키가 없으면 0입니다.
힌트 2
`count`가 정확하도록, 칸을 0으로 바꾸면 그 칸을 지워야 합니다.
힌트 3
열을 삭제할 때는 맵을 다시 만드세요. 그 열은 버리고, 더 큰 열 번호는 하나씩 줄입니다.
예상 복잡도
시간 O(q × s), 추가 공간 O(s), s = 저장된 칸 수
참고 자료
이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.