문제 소개
정수로 구성된 행렬(matrix)이 주어졌을 때, 모든 요소가 동일한 값으로 이루어진 행의 개수를 찾는 것이 이 글의 목표입니다.
예를 들어 다음과 같은 5×4 행렬이 있다고 가정해 보겠습니다.
| 1 | 5 | 1 | 3 | 1 |
| 1 | 1 | 1 | 1 | 1 |
| 5 | 3 | 2 | 3 | 5 |
| 7 | 7 | 7 | 7 | 7 |
이 경우 답은 2입니다. 인덱스 1의 행(모든 요소가 1)과 인덱스 3의 행(모든 요소가 7)만 동일한 요소로 구성되어 있기 때문입니다.
아래 예제를 통해 좀 더 자세히 살펴보겠습니다.
예제 1
입력:
matrix =
[ 1 1 1 1 ]
[ 2 3 2 7 ]
[ 3 3 3 3 ]
출력: 동일한 요소로 구성된 행의 개수 − 2
설명: 0번째 행은 모든 요소가 1이고, 2번째 행은 모든 요소가 3이므로 총 2개의 행이 조건을 만족합니다.
예제 2
입력:
matrix =
[ 1 2 3 4 ]
[ 1 2 3 4 ]
[ 1 2 3 4 ]
출력: 동일한 요소로 구성된 행의 개수 − 0
설명: 세 행 모두 서로 다른 요소들을 포함하고 있으므로 조건을 만족하는 행은 하나도 없습니다.
접근 방법
행렬을 vector<vector<int>> 형태로 받아 처리합니다. 각 행을 순회하면서 해당 행의 요소들을 set<int>에 삽입합니다. set은 중복을 허용하지 않는 자료구조이므로, 한 행의 순회가 끝난 뒤 set의 크기가 1이라면 그 행의 모든 요소가 동일하다는 의미입니다.
- 행렬을 vector<vector<int>> 타입으로 선언하고 초기화합니다.
- matrix.size()를 사용하여 행렬의 크기(행 수)를 계산합니다.
- same_rows(vector<vector<int>> matrix, int size) 함수는 행렬과 그 크기를 받아 동일한 요소로 구성된 행의 개수를 반환합니다.
- 초기 count 값을 0으로 설정합니다.
- for 반복문으로 i = 0부터 i < size까지 각 행을 순회합니다.
- 각 행에 대해 j = 0부터 j < matrix[i].size()까지 열을 순회합니다.
- 현재 행의 요소를 저장할 set<int> set_row를 생성합니다.
- set_row.insert(matrix[i][j])를 통해 현재 행의 요소들을 set에 삽입합니다.
- 행 순회가 끝나면 set_row의 크기를 확인합니다. 크기가 1이면 해당 행은 모든 요소가 동일하므로 count를 증가시킵니다.
- 모든 행에 대한 반복이 끝나면 count를 최종 결과로 반환합니다.
C++ 코드 예제
#include <bits/stdc++.h>
using namespace std;
int same_rows(vector<vector<int>> matrix, int size){
int count = 0;
for (int i = 0; i < size; i++){
set<int> set_row;
for (int j = 0; j < matrix[i].size(); j++){
set_row.insert(matrix[i][j]);
}
int set_size = set_row.size();
if (set_size == 1){
count++;
}
}
return count;
}
int main(){
vector<vector<int>> matrix = {
{ 2, 2, 2, 2 },
{ 5, 5, 5, 5 },
{ 2, 2, 2, 2 },
{ 5, 5, 5, 5 }
};
int size = matrix.size();
cout << "동일한 요소로 구성된 행의 개수: " << same_rows(matrix, size);
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 출력을 얻을 수 있습니다.
동일한 요소로 구성된 행의 개수: 4
마무리 및 복잡도 분석
이 문제는 set 자료구조의 중복 제거 특성을 활용하면 매우 간단하게 해결할 수 있습니다. 각 행마다 set의 크기만 확인하면 되며, 전체 시간 복잡도는 O(N×M)입니다(N은 행 수, M은 열 수).
성능이 중요한 환경이라면 set 대신 각 행의 첫 번째 요소와 나머지 요소를 직접 비교하는 방식을 사용할 수 있습니다. 이 방법은 추가 메모리 할당 없이 불일치를 발견하는 즉시 다음 행으로 넘어갈 수 있어 실제 실행 속도가 더 빠른 경우가 많습니다.