문제 소개
리스트의 리스트(list of lists) 형태로 주어진 nums의 모든 원소를 대각선 순서(diagonal order)대로 출력하는 것이 이번 문제의 목표입니다.
예를 들어 다음과 같은 입력이 주어진 경우,
출력은 아래와 같습니다.
[1, 6, 2, 8, 7, 3, 9, 4, 12, 10, 5, 13, 11, 14, 15, 16]
해결 접근 방법
핵심 아이디어는 각 원소가 속한 대각선 번호를 계산한 뒤, 그 번호를 기준으로 정렬하는 것입니다. 행 인덱스와 열 인덱스의 합(i + j)이 같은 원소들은 모두 같은 대각선 위에 위치한다는 성질을 활용합니다.
결과를 저장할 배열
ret을 정의합니다.원소 값과 좌표 정보를 함께 담을 2차원 배열
v를 정의합니다.i := 0부터 nums의 크기까지 반복하면서 −
j := 0부터 nums[i]의 크기까지 반복하며 −
{ nums[i][j], i, j } 형태의 튜플을 v의 끝에 삽입합니다.
사용자 정의 비교 함수를 이용해 배열 v를 정렬합니다. 대각선 번호(i + j)가 작은 순서대로, 같은 대각선 안에서는 행 번호(i)가 큰 순서대로 정렬됩니다.
정렬된 v의 각 원소(it)에 대해 −
실제 값인 it[0]을 ret의 끝에 삽입합니다.
ret을 반환합니다.
비교 함수의 동작 원리
cmp 함수는 두 원소 a, b에 대해 먼저 각각의 대각선 번호(sum1 = a[1] + a[2], sum2 = b[1] + b[2])를 계산합니다. 두 번호가 같다면 행 인덱스가 큰 쪽이 앞에 오도록(a[1] > b[1]) 처리하고, 그렇지 않으면 대각선 번호가 작은 쪽이 앞에 오도록(sum1 < sum2) 정렬합니다. 이는 대각선을 왼쪽 아래에서 오른쪽 위 방향으로 순회하는 규칙을 그대로 반영한 것입니다.
C++ 구현 예제
아래 코드를 통해 더 잘 이해할 수 있습니다 −
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<int> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
static bool cmp(vector <int>& a, vector <int>& b ){
int sum1 = a[1] + a[2];
int sum2 = b[1] + b[2];
return sum1 == sum2 ? a[1] > b[1] : sum1 < sum2;
}
vector<int> findDiagonalOrder(vector& nums) {
vector<int> ret;
vector<vector<int> > v;
for (int i = 0; i < nums.size(); i++) {
for (int j = 0; j < nums[i].size(); j++) {
v.push_back({ nums[i][j], i, j });
}
}
sort(v.begin(), v.end(), cmp);
for (auto& it : v)
ret.push_back(it[0]);
return ret;
}
};
main(){
Solution ob;
vector<vector<int>> v = {{1,2,3,4,5},{6,7},{8},{9,10,11},{12,13,14,15,16}};
print_vector(ob.findDiagonalOrder(v));
}입력
{{1,2,3,4,5},{6,7},{8},{9,10,11},{12,13,14,15,16}}출력
[1, 6, 2, 8, 7, 3, 9, 4, 12, 10, 5, 13, 11, 14, 15, 16]