C++에서 지나가는 자동차 쌍 개수 세기: 단순 탐색부터 O(N) 최적화까지

문제 개요

길이가 N인 배열이 주어지며, 배열에는 0과 1만 들어 있습니다. 값 1은 서쪽 방향으로 달리는 자동차를, 값 0은 동쪽 방향으로 달리는 자동차를 의미합니다.

두 자동차 A와 B가 0 ≤ A < B < N 조건을 만족하고, A가 동쪽으로(0) B가 서쪽으로(1) 진행한다면 이를 '지나가는 자동차 쌍'으로 세어 1씩 카운트합니다. 즉, 0의 인덱스가 1의 인덱스보다 앞선 (0, 1) 쌍의 개수를 구하는 문제입니다.

예시를 통해 살펴보겠습니다.

입력 − arr[] = {1, 0, 1, 0, 1}

출력 − 지나가는 자동차 쌍의 개수: 3

설명 − 0의 인덱스가 1의 인덱스보다 작은 쌍은 (arr[1], arr[2]), (arr[1], arr[4]), (arr[3], arr[4])로 총 3개입니다.

입력 − arr[] = {1, 0, 0, 0, 0}

출력 − 지나가는 자동차 쌍의 개수: 0

설명 − 0의 인덱스가 1의 인덱스보다 작은 (0, 1) 쌍이 하나도 존재하지 않습니다.

방법 1: 단순 탐색 (이중 루프)

가장 직관적인 방법은 두 개의 for 반복문을 사용하는 것입니다. 배열을 순회하다가 0을 만나면, 그 지점부터 배열의 끝까지 한 번 더 순회하며 1을 발견할 때마다 카운트를 증가시킵니다.

0과 1로 이루어진 배열 arr[]를 준비합니다.
함수 count_cars(int arr[], int size)는 배열과 배열의 길이를 입력받아 지나가는 자동차 쌍의 개수를 반환합니다.
카운트(count)를 0으로 초기화합니다.
i = 0부터 i < size - 1까지 바깥 루프로 배열을 순회합니다.
arr[i]가 0이라면, j = i + 1부터 j < size까지 안쪽 루프로 다시 순회합니다.
arr[j]가 1일 때마다 카운트를 1씩 증가시킵니다. 이는 (arr[i], arr[j])가 (0, 1)이고 i < j 조건을 만족하는 유효한 쌍이기 때문입니다.
모든 순회가 끝나면 전체 쌍의 개수를 얻습니다.
count를 결과값으로 반환합니다.

이 방식은 가능한 모든 쌍을 검사하므로 시간 복잡도가 O(N²)입니다. 배열이 길어질수록 실행 시간이 빠르게 늘어난다는 단점이 있습니다.

방법 2: 효율적인 접근 (O(N))

이번에는 배열을 뒤에서부터 순회하는 방법입니다. 끝에서부터 차례대로 살피며 1의 개수를 temp 변수에 누적하고, 0을 만날 때마다 현재까지 세어 온 1의 개수(temp)만큼 새로운 쌍이 생기므로 이를 카운트에 더해줍니다.

0과 1로 이루어진 배열 arr[]를 준비합니다.
함수 count_cars(int arr[], int size)는 배열과 길이를 입력받아 지나가는 자동차 쌍의 개수를 반환합니다.
카운트(count)와 임시 변수(temp)를 0으로 초기화합니다.
while 반복문으로 size ≥ 1 조건이 유지되는 동안 배열을 뒤에서부터 순회합니다.
arr[size - 1]이 1이라면, 지금까지 발견한 1의 개수를 나타내는 temp를 1 증가시킵니다.
arr[size - 1]이 0이라면, 이 0은 뒤쪽에 있는 모든 1들보다 인덱스가 앞서므로 temp개의 쌍이 추가로 성립합니다. count = count + temp로 갱신합니다.
size를 1 감소시켜 다음 원소로 이동합니다.
순회가 끝나면 전체 개수를 얻습니다.
count를 결과값으로 반환합니다.

배열을 단 한 번만 순회하므로 시간 복잡도는 O(N)이며, 단순 탐색 방식에 비해 훨씬 효율적입니다.

예제 코드 (단순 탐색)

#include<bits/stdc++.h>
using namespace std;
int count_cars(int arr[], int size){
    int count = 0;
    for (int i=0; i<size-1; i++){
        if(arr[i] == 0){
            for (int j=i+1; j<size; j++)
            if (arr[j]==1){
                count++;
            }
        }
    }
    return count;
}
int main(){
    int arr[] = {1, 1, 0, 0, 1};
    int size = sizeof(arr)/sizeof(arr[0]);
    cout<<"지나가는 자동차 쌍의 개수: "<<count_cars(arr, size);
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 출력이 생성됩니다 −

지나가는 자동차 쌍의 개수: 2

예제 코드 (효율적인 접근)

#include<bits/stdc++.h>
using namespace std;
int count_cars(int arr[], int size){
    int count = 0;
    int temp = 0;
    while (size >= 1){
        if (arr[size-1] == 1){
            temp++;
        }
        else{
            count = count + temp;
        }
        size--;
    }
    return count;
}
int main(){
    int arr[] = {1, 1, 0, 1, 1};
    int size = sizeof(arr)/sizeof(arr[0]);
    cout<<"지나가는 자동차 쌍의 개수: "<<count_cars(arr, size);
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 출력이 생성됩니다 −

지나가는 자동차 쌍의 개수: 2

마무리

지나가는 자동차 쌍 문제는 배열 순회 방향과 누적 카운팅만 잘 활용하면 O(N²)에서 O(N)으로 성능을 크게 개선할 수 있는 대표적인 예제입니다. 입력 배열이 커질수록 두 방식의 실행 시간 차이가 극명해지므로, 코딩 테스트나 실무에서는 반드시 최적화된 접근 방식을 사용하는 것이 좋습니다.