[PS] 배열에서 숫자 개수 세기 (cpp)

이 포스팅은 숫자의 범위가 작은 경우일 때 계수 정렬을 활용하는 방법을 기록했다. 수의 범위를 1~10,000 정도라고 가정하고 시작한다.

1차원 배열

1차원 배열에서 입력받은 수들의 횟수를 아래와 같은 방법으로 셀 수 있다.
cnt는 수의 범위에 맞는 배열이고, x는 항상 양수라고 가정한다.

int n,x,cnt[10001];

cin >> n;
for (int i = 0 ; i < n; i++) {
    cin >> x;
    cnt[x]++;
}

2차원 배열

2차원 배열에서도 입력받은 수들의 횟수를 세고 싶다면 1차원 배열과 같은 방법으로 셀 수 있다.
2차원 배열에서 행 마다 어떤 숫자 ‘x’ 가 등장했는 지 확인해보려고 한다. 예를 들면 3x3 의 2차원 배열이 있을 때 1행,2행,3행에 2라는 숫자가 모두 등장했는지 확인하는 것이다.

for(int i = 0 ; i < n; i++) {
    for (int j = 0 ; j < m; j++) {
        cin >> num;
        if(num == x && cnt[x] == i) cnt[x] = i+1;
    }
}
if(cnt[x] == n) cout << "OK";

위 코드는 매 행에서 숫자 x가 입력되면 cnt 배열의 값을 행+1 로 해준다.
만약 1행에서 x가 입력되고, 2행에서 x가 입력되지 않고, 3행에서 x가 입력되면 cnt[x]의 값은 1이고, i의 값은 2이기 때문에 cnt[x]의 값은 3이 되지 못한다.

이 코드를 어떤 숫자 ‘x’가 아니라 모든 숫자에 대해 확인해보려면 아래와 같이 쓸 수 있다.

for(int i = 0 ; i < n; i++) {
    for (int j = 0 ; j < m; j++) {
        cin >> num;
        if(cnt[num] == i) cnt[num] = i+1;
    }
}
for (int i = 0; i < 10001; i++)
    if(cnt[i] == n) cout << i << "는 매 행마다 한 번 이상은 입력되었다";