길이가 모두 동일한 문자열 배열이 주어졌을 때, 오름차순으로 정렬되어 있지 않은 열(column)의 개수를 구하는 것이 목표입니다. 여기서 열이란 각 문자열에서 같은 위치에 있는 문자들의 집합을 의미합니다. 즉, 첫 번째 문자열의 첫 문자와 두 번째 문자열의 첫 문자를 비교하고, 이러한 방식으로 마지막 문자열까지 비교하여 오름차순이 아니라면 카운트를 증가시킵니다. 이 작업을 두 번째 문자, 세 번째 문자에 대해서도 차례로 반복합니다.
입력 예시 1
Arr[] = { "abc", "bcd", "def" }
출력
정렬되지 않은 열의 개수: 0
설명
각 열을 기준으로 살펴보면 다음과 같습니다.
- 열 1: 인덱스 0의 문자들 — a < b < d
- 열 2: 인덱스 1의 문자들 — b < c < e
- 열 3: 인덱스 2의 문자들 — c < d < f
모든 열의 문자들이 오름차순으로 정렬되어 있으므로 정렬되지 않은 열의 개수는 0입니다.
입력 예시 2
Arr[] = { "dbd", "faf", "eeg" }
출력
정렬되지 않은 열의 개수: 2
설명
- 열 1: d < f > e — 오름차순 아님
- 열 2: b > a < e — 오름차순 아님
- 열 3: d < f < g — 오름차순
열 1과 열 2가 오름차순으로 정렬되어 있지 않으므로 개수는 2입니다.
접근 방법
아래 프로그램에 적용된 접근 방식은 다음과 같습니다.
- 같은 길이의 문자열들을 저장하기 위해 2차원 문자 배열 arr[][]를 사용합니다.
- countCols() 함수는 문자열 배열, 문자열의 개수(n), 각 문자열의 길이(len)를 입력받아 오름차순으로 정렬되지 않은 열의 개수를 반환합니다.
- 카운트 변수를 0으로 초기화합니다.
- 바깥쪽 for 루프는 현재 검사 중인 열, 즉 모든 문자열에 공통으로 적용되는 문자 인덱스를 나타냅니다.
- 안쪽 for 루프를 사용해 해당 열의 문자들을 위에서 아래로 순회하며 인접한 두 문자를 비교합니다.
- 위쪽 문자열의 문자가 바로 아래 문자열의 문자보다 크면(str[i][j] > str[i+1][j]) 해당 열은 오름차순이 아니므로 카운트를 증가시키고 다음 열로 넘어갑니다.
- 모든 열에 대한 검사가 끝나면 count에 저장된 결과를 반환합니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
// 오름차순으로 정렬되지 않은 열의 개수를 반환하는 함수
int countCols(char str[][4], int n, int len){
int count = 0;
// 각 열(문자 인덱스)별로 위에서 아래로 검사
for(int j = 0; j < len; j++){
bool isSorted = true;
for(int i = 0; i < n - 1; i++){
if(str[i][j] > str[i+1][j]){ // 앞 문자가 더 크면 정렬되지 않음
isSorted = false;
break;
}
}
if(!isSorted)
count++;
}
return count;
}
int main(){
char arr[3][4] = {"dbd", "faf", "eeg"};
cout << "\n정렬되지 않은 열의 개수: " << countCols(arr, 3, 3);
return 0;
}
출력
정렬되지 않은 열의 개수: 2
복잡도 분석
- 시간 복잡도: O(n × len) — 각 열마다 n개의 문자열의 문자를 한 번씩 비교합니다.
- 공간 복잡도: O(1) — 추가 메모리 없이 상수 공간만 사용합니다.