문제 설명
정사각 행렬 mat[][]가 주어졌을 때, 행렬에 들어 있는 원소 중 값이 x와 같은 항목이 몇 개인지 세는 것이 이번 문제의 목표입니다. 여기서 말하는 '특수 행렬'은 원소가 mat[i][j] = i × j와 같은 규칙으로 구성된 행렬을 의미할 수 있지만, 아래에서 소개하는 방법은 어떤 형태의 행렬에도 동일하게 적용할 수 있습니다.
행렬은 숫자나 원소를 행(row)과 열(column)의 형태로 배치해 표현하는 2차원 배열입니다.
그럼 구체적인 예시를 통해 문제의 해결 방법을 하나씩 살펴보겠습니다.
예시 1
입력 −
matrix[row][col] = {
{1, 2, 3},
{3, 4, 3},
{3, 4, 5}};
x = 3출력 −
Count of entries equal to x in a special matrix: 4
위 행렬에서 값이 3인 원소는 총 4개(1행 3열, 2행 1열, 2행 3열, 3행 1열)이므로 결과는 4가 됩니다.
예시 2
입력 −
matrix[row][col] = {
{10, 20, 30},
{30, 40, 30},
{30, 40, 50}};
x = 30출력 −
Count of entries equal to x in a special matrix: 4
x = 30인 경우에도 값이 30인 원소가 4개 있으므로 동일하게 4가 출력됩니다.
접근 방법
- 행렬 mat[][]와 찾고자 하는 값 x를 입력값으로 받습니다.
- count 함수 안에서 x와 같은 항목의 개수를 셉니다.
- 행렬 전체를 순회하면서 mat[i][j] == x 조건을 만족하는 지점을 발견하면 카운트를 1씩 증가시킵니다.
- 최종적으로 카운트 값을 반환한 뒤 결과로 출력합니다.
이 방식은 행렬의 모든 원소를 한 번씩 확인하므로 시간 복잡도는 O(row × col)이며, 별도의 추가 메모리 없이 O(1)의 공간 복잡도로 해결할 수 있습니다.
예제 코드
#include<bits/stdc++.h>
using namespace std;
#define row 3
#define col 3
// x와 같은 항목의 개수를 세는 함수
int count (int matrix[row][col], int x){
int count = 0;
// 행렬을 순회하며 x와 같은 값 찾기
for(int i = 0 ;i<row;i++){
for(int j = 0; j<col; j++){
if(matrix[i][j] == x){
count++;
}
}
}
// 개수 반환
return count;
}
int main(){
int matrix[row][col] = {
{1, 2, 3},
{3, 4, 3},
{3, 4, 5}
};
int x = 3;
cout<<"Count of entries equal to x in a special matrix: "<<count(matrix, x);
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 출력을 얻을 수 있습니다.
Count of entries equal to x in a special matrix: 4
이처럼 이중 반복문을 활용해 행렬을 선형 탐색하는 것만으로도 특정 값의 등장 횟수를 손쉽게 구할 수 있습니다. 다만 행렬의 크기가 커질수록 탐색에 걸리는 시간도 함께 늘어나므로, 대규모 데이터를 다룰 때는 인덱싱이나 행렬의 수학적 성질을 활용한 최적화 방법을 함께 고려해 보는 것이 좋습니다.