[코드트리] 행복한 수열의 개수

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

1. 구현 아이디어

간단한 완전탐색 문제이다.

 

한 행씩 순회하면서 동일한 원소를 의미하는 target 변수를 만든다.

최초에는 그 값을 0번째 원소로 두고, 다음 원소와 비교하며 만약에 같다면 동일한 원소가 몇 번 나왔는지를 세는 변수인 cnt를 1 증가시켜준다.

만약 다르다면, 해당 원소를 target으로 갱신하고, cnt는 1로 초기화해준 뒤 다음 원소와 비교해준다.

 

cnt가 m 이상일 경우 해당 행은 행복한 수열이므로 행복한 수열의 개수를 세는 변수 ret을 1 증가시켜준다.

 

이번 문제나 백준 14890번 경사로 문제처럼 행과 열을 모두 순회해야 하는 경우가 있다.

 

이럴 때는 하나의 2차원 배열에서 인덱스를 조정하며 문제를 푸는 것보다, 전치행렬(열이 행이 되도록) 2차원 배열을 하나 더 만들어주는 것이 편리하다.

전치행렬

 

 

2. 전체 코드

#include <iostream>
#include <vector>

using namespace std;

typedef vector<vector<int>> vvi;

int countHappy(vvi &arr, int m) {
    int ret = 0;
    
    int n = arr.size();
    for (int i = 0; i < n; i++) {
        int cnt = 0; // 동일한 원소가 연속해서 몇 번 나왔는지
        int target = arr[i][0]; // 동일한 원소의 기준이 되는 값

		// 한 행씩 순회하면서 행복한 수열을 찾는다
        for (int j = 0; j < n; j++) {
        	// 이전 원소와 동일한 원소일 경우 cnt++ 
            if (target == arr[i][j]) cnt++;
            else {
                target = arr[i][j];
                cnt = 1;
            }
			
            // cnt가 m개가 되면 해당 줄을 더 이상 볼 필요 없음
            if (cnt == m) {
                ret++;
                break;
            }
        }

    }

    return ret;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, m; // 격자의 크기, 연속해야 하는 숫자의 수
    cin >> n >> m;

    vvi rows = vvi(n, vector<int>(n, 0));
    vvi cols = vvi(n, vector<int>(n, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int elem;
            cin >> elem;
            rows[i][j] = elem;
            cols[j][i] = elem;
        }
    }

    cout << countHappy(rows, m) + countHappy(cols, m) << '\n';
    return 0;
}

 

행을 순회할 때와 열을 순회할 때 파라미터만 다르고 로직은 동일하기 때문에 countHappy라는 함수로 분리하여 코드를 작성해주었다.

countHappy 구현 내용은 구현 아이디어에서 설명한 것과 동일하다.