개요
이 튜토리얼에서는 C++을 활용해 행렬(matrix) 안에서 오름차순 또는 내림차순으로 정렬된 행의 개수를 구하는 프로그램을 만들어 보겠습니다.
문제 정의
m×n 크기의 2차원 행렬이 주어졌을 때, 각 행이 오름차순(비내림차순)이거나 내림차순(비오름차순)으로 정렬되어 있는지 판별하고, 조건을 만족하는 행의 총 개수를 반환하는 것이 목표입니다.
예를 들어 아래와 같은 4×5 행렬을 살펴보겠습니다.
{1, 2, 3, 4, 5} → 오름차순 정렬 O
{4, 3, 1, 2, 6} → 정렬되지 않음 X
{8, 7, 6, 5, 4} → 내림차순 정렬 O
{5, 7, 8, 9, 10} → 오름차순 정렬 O위 행렬에서 정렬된 행은 총 3개입니다.
접근 방법
핵심 아이디어는 간단합니다. 각 행을 두 방향으로 훑으면서 두 가지 조건을 각각 검사합니다.
- 오름차순 검사: 왼쪽에서 오른쪽으로 이동하며 인접한 두 요소를 비교합니다. 앞 요소보다 작거나 같은 값이 등장하면 해당 행은 오름차순이 아닙니다.
- 내림차순 검사: 반대로 오른쪽에서 왼쪽으로 이동하며 인접한 두 요소를 비교합니다. 뒤 요소보다 작거나 같은 값이 등장하면 내림차순이 아닙니다.
- 두 검사 중 하나라도 끝까지 통과하면 그 행을 '정렬된 행'으로 간주하고 카운트를 1 증가시킵니다.
C++ 구현 코드
#include <bits/stdc++.h>
#define MAX 100
using namespace std;
// 정렬된 행의 개수를 세는 함수
int count_srows(int mat[][MAX], int r, int c){
int result = 0;
// 1) 오름차순으로 정렬된 행 검사
for (int i = 0; i < r; i++){
int j;
for (j = 0; j < c - 1; j++)
if (mat[i][j + 1] <= mat[i][j])
break;
if (j == c - 1)
result++;
}
// 2) 내림차순으로 정렬된 행 검사
for (int i = 0; i < r; i++){
int j;
for (j = c - 1; j > 0; j--)
if (mat[i][j - 1] <= mat[i][j])
break;
if (c > 1 && j == 0)
result++;
}
return result;
}
int main(){
int m = 4, n = 5;
int mat[][MAX] = {{1, 2, 3, 4, 5}, {4, 3, 1, 2, 6},
{8, 7, 6, 5, 4}, {5, 7, 8, 9, 10}};
cout << count_srows(mat, m, n);
return 0;
}실행 결과
3
코드 동작 원리
첫 번째 루프에서는 각 행의 요소를 순서대로 비교합니다. mat[i][j+1]이 mat[i][j]보다 작거나 같으면 오름차순 조건이 깨진 것이므로 즉시 반복문을 종료합니다. 반복문이 마지막 열(c-1)까지 도달했다면 해당 행은 오름차순으로 정렬되어 있으므로 result를 증가시킵니다.
두 번째 루프는 같은 논리를 역방향으로 수행해 내림차순 여부를 확인합니다. 여기에 c > 1 조건을 추가한 이유는, 열이 하나뿐인 행렬에서 같은 행이 중복해서 카운트되는 것을 방지하기 위함입니다.
참고로 모든 요소가 같은 상수 행은 오름차순과 내림차순 양쪽 조건을 모두 만족하므로 이 알고리즘에서는 두 번 카운트됩니다. 이런 경우를 한 번만 세고 싶다면 두 검사를 하나의 루프로 합치거나 중복 여부를 따로 처리해야 합니다.
시간 복잡도
행렬의 모든 요소를 최대 두 번씩 방문하므로 시간 복잡도는 O(m×n)이며, 별도의 추가 공간을 사용하지 않으므로 공간 복잡도는 O(1)입니다.
마무리
이처럼 각 행을 선형 탐색하면서 인접한 요소만 비교하면 정렬 여부를 손쉽게 판별할 수 있습니다. 데이터 유효성 검사나 전처리 단계에서 실용적으로 활용할 수 있는 기본적인 배열·행렬 처리 기법이니 꼭 익혀 두시길 바랍니다.