[MEMO] 배열을 탐색하며 원소들을 그룹화 하는 방법 관하여

배열을 탐색하며 그룹화 🧐

BOJ 2879 를 해결하는 과정에서 생각하게 된 방법이다.

문제의 해결방법은 비교적 간단하게 생각해 낼 수 있었다. 그룹으로 묶여져 있는 수열들의 갯수를 매번 카운팅해가며 모든 값을 더하면 되었다.

그러나 그룹으로 묶여져 있는 수열들의 갯수를 파악하는데 생각보다 구현이 어려웠다. 다음과 같은 조건으로 이루어져 있었다.

• 수는 음수와 양수 두 그룹으로 이루어져 있다.
• 0은 그 어떤 그룹에도 속하지 않는다.
• 연속으로 붙어있는 음수, 양수는 하나의 그룹이다.

처음에는 배열을 순회하며 두 인덱스씩 비교해나가면서 서로 다른 두 값이 들어올 때 마다 카운팅하는 방식으로 진행했다.

그러나 많은 예외조건이 생겼으며 그에 따라 코드가 복잡해질 뿐더러 모든 예외상황을 처리하려다 보니 생각치도 못한 오류가 많이 발생했다.

여러 고민을 걸쳐 다음과 같은 방법을 통해 구현했다.

• 별도의 상태를 정의하여 배열을 순회할 때 수의 값과 현재의 상태까지 고려하여 카운팅을 진행한다.
• 상태의 조건
  • 음수를 만남
  • 양수를 만남
  • 0을 만남

즉, 별도의 상태를 정의하여 이전의 지나왔던 값을 기억하도록 한 것이다. 이러한 상태를 정의하면 다음과 같은 연산에서 카운팅이 진행된다.

• 양수를 만남 → 현재 상태를 양수를 만난 상태로 변경
  • 이전에 음수를 만났었다. → 카운팅
  • 이전에 0을 만났었다. → 카운팅
  • 이전에 양수를 만났었다. → 카운팅 안함

• 음수를 만남 → 현재 상태를 음수를 만난 상태로 변경
  • 이전에 양수를 만났었다. → 카운팅
  • 이전에 0을 만났었다. → 카운팅
  • 이전에 음수를 만났었다. → 카운팅 안함

• 0을 만남 → 현재 상태를 0을 만난 상태로 변경

즉, 처음 음수 혹은 양수의 그룹을 만났을 때 마다 카운팅을 진행하겠다는 의미이다. 다음은 실제로 BOJ 2879을 풀면서 작성했던 코드이다.

		int cnt = 0; // 그룹의 수
        int cdt; // 상태 조건
        
        cdt = 0;
        for(int i=0; i<vec.size(); i++){
            if(vec[i] > 0){
                if(cdt == 0 || cdt == -1){
                    cnt ++;
                }
                cdt = 1;
            }
            
            else if(vec[i] < 0){
                if(cdt == 1 || cdt == 0){
                    cnt ++;
                }
                cdt = -1;
            }

            else{
                cdt = 0;
            }
        }

여기서 vec의 경우 우리가 탐색할 배열이며, cnt는 카운트한 그룹의 수, cdt의 경우 앞서 정의한 상태이다.

실제로 동작해보면 정상적으로 잘 카운트되는 것을 확인할 수 있다.