이 튜토리얼에서는 C++를 사용해 행렬(2차원 배열)에서 내림차순으로 정렬된 열의 개수를 구하는 방법을 알아봅니다.
R×C 크기의 행렬이 주어졌을 때, 각 열의 원소들이 위에서 아래로 갈수록 같아지거나 작아지는(내림차순) 형태를 띠는 열이 몇 개인지 세는 것이 목표입니다.
접근 방법
핵심 아이디어는 단순합니다. 각 열을 하나씩 순회하면서, 해당 열의 인접한 두 원소가 항상 mat[j-1][i] >= mat[j][i] 조건(위 원소가 아래 원소보다 크거나 같음)을 만족하는지 검사합니다.
검사 도중 조건이 한 번이라도 깨지면 그 열은 내림차순이 아니므로 즉시 다음 열로 넘어가고, 끝까지 조건을 통과한 열만 결과값에 포함시킵니다.
예제 코드
#include <bits/stdc++.h>
#define MAX 100
using namespace std;
// 내림차순으로 정렬된 열의 개수를 세는 함수
int count_dcolumns(int mat[][MAX], int r, int c) {
int result = 0;
for (int i = 0; i < c; i++) { // 각 열(column)에 대해
int j;
// 맨 아래 행부터 위로 올라가며 내림차순 여부 검사
for (j = r - 1; j > 0; j--)
if (mat[j - 1][i] < mat[j][i])
break; // 내림차순이 깨진 지점에서 중단
if (j == 0) // 끝까지 통과한 열만 카운트
result++;
}
return result;
}
int main() {
int m = 2, n = 2;
int mat[][MAX] = {{1, 3}, {0, 2}};
cout << count_dcolumns(mat, m, n);
return 0;
}
실행 결과
2
코드 동작 설명
예제로 사용된 행렬은 다음과 같습니다.
1 3
0 2
- 첫 번째 열: 1 → 0 으로 값이 감소하므로 내림차순입니다.
- 두 번째 열: 3 → 2 로 값이 감소하므로 내림차순입니다.
두 열 모두 조건을 만족하므로 최종 출력은 2가 됩니다.
함수 내부의 안쪽 반복문은 맨 아래 행(r-1)부터 시작해 위로 이동하며 비교를 수행합니다. mat[j-1][i] < mat[j][i], 즉 위 원소가 아래 원소보다 작아 내림차순이 깨지는 순간 break로 반복문을 탈출합니다. 반복문이 중단 없이 끝까지 실행되어 j가 0이 되었다면 그 열 전체가 내림차순이라는 의미이므로 카운트를 1 증가시킵니다.
복잡도 분석
모든 열을 한 번씩 확인하고 각 열에서 최대 R번의 비교를 수행하므로 시간 복잡도는 O(R×C)이며, 추가 메모리를 사용하지 않으므로 공간 복잡도는 O(1)입니다.