[알고리즘] 11. 카운팅 배열

[알고리즘] 11. 카운팅 배열

지난 글에서는 숫자 처리와 자리수에 대해 정리했습니다. 이번 글에서는 알고리즘 기초 구현에서 정말 자주 사용하는 카운팅 배열에 대해 알아보겠습니다.

카운팅 배열은 숫자나 문자가 몇 번 등장했는지 빠르게 세기 위해 사용하는 배열입니다. 처음에는 단순해 보이지만, 빈도수 계산, 중복 확인, 최빈값 찾기, 알파벳 개수 세기 같은 문제에서 매우 자주 사용됩니다.

카운팅 배열은 값의 등장 횟수를 배열의 인덱스를 이용해 저장하는 방법입니다.

---

1. 카운팅 배열이 필요한 이유

배열 안에 어떤 숫자가 몇 번 나왔는지 세야 하는 상황을 생각해보겠습니다.

1 3 2 1 3 1 2

이 숫자들에서 1은 3번, 2는 2번, 3은 2번 등장합니다. 이런 등장 횟수를 저장하기 위해 카운팅 배열을 사용할 수 있습니다.

숫자	등장 횟수
1	3번
2	2번
3	2번

값이 등장할 때마다 해당 위치의 개수를 1씩 증가시키면 됩니다.

---

2. 기본 아이디어

카운팅 배열의 핵심은 값을 인덱스로 사용한다는 점입니다.

예를 들어 숫자 3이 등장하면 count[3]을 1 증가시킵니다. 숫자 1이 등장하면 count[1]을 1 증가시킵니다.

숫자 1 등장 → count[1]++
숫자 2 등장 → count[2]++
숫자 3 등장 → count[3]++

이렇게 하면 숫자별 등장 횟수를 배열에 저장할 수 있습니다.

카운팅 배열에서는 데이터의 값이 곧 배열의 인덱스가 됩니다.

---

3. 숫자 등장 횟수 세기

다음 배열에서 각 숫자가 몇 번 등장하는지 세어보겠습니다. 숫자는 1부터 5까지 나온다고 가정하겠습니다.

int[] numbers = {1, 3, 2, 1, 3, 1, 2};

int[] count = new int[6];

for (int i = 0; i < numbers.length; i++) {
    count[numbers[i]]++;
}

for (int i = 1; i < count.length; i++) {
    System.out.println(i + "의 개수: " + count[i]);
}

출력 결과는 다음과 같습니다.

1의 개수: 3
2의 개수: 2
3의 개수: 2
4의 개수: 0
5의 개수: 0

여기서 count 배열의 크기를 6으로 만든 이유는 인덱스 5까지 사용하기 위해서입니다. 인덱스는 0부터 시작하므로 숫자 5를 count[5]에 저장하려면 배열 길이가 최소 6이어야 합니다.

---

4. count[numbers[i]]++ 이해하기

카운팅 배열에서 가장 중요한 코드는 아래 한 줄입니다.

count[numbers[i]]++;

처음 보면 조금 헷갈릴 수 있습니다. 하지만 하나씩 나누어 보면 어렵지 않습니다.

예를 들어 numbers[i] 값이 3이라면 아래와 같은 의미가 됩니다.

numbers[i] = 3
count[numbers[i]]++
count[3]++

즉 숫자 3이 등장했으므로 count[3]을 1 증가시키는 것입니다.

현재 값	증가하는 위치
1	count[1]++
2	count[2]++
3	count[3]++

이 방식 덕분에 모든 값을 하나씩 비교하지 않아도, 등장 횟수를 빠르게 저장할 수 있습니다.

---

5. 특정 숫자가 몇 번 나왔는지 확인하기

카운팅 배열을 만들어두면 특정 숫자의 등장 횟수를 바로 확인할 수 있습니다.

int[] numbers = {1, 3, 2, 1, 3, 1, 2};

int[] count = new int[6];

for (int i = 0; i < numbers.length; i++) {
    count[numbers[i]]++;
}

System.out.println(count[1]);
System.out.println(count[2]);
System.out.println(count[3]);

출력 결과는 다음과 같습니다.

3
2
2

count[1]은 숫자 1의 등장 횟수, count[2]는 숫자 2의 등장 횟수, count[3]은 숫자 3의 등장 횟수를 의미합니다.

카운팅 배열을 만들면 특정 값의 등장 횟수를 O(1)에 확인할 수 있습니다.

---

6. 중복 값 확인하기

카운팅 배열은 중복된 값이 있는지 확인할 때도 유용합니다. 등장 횟수가 2 이상인 값이 있다면 중복이 존재한다는 뜻입니다.

int[] numbers = {1, 2, 3, 2, 5};

int[] count = new int[6];

for (int i = 0; i < numbers.length; i++) {
    count[numbers[i]]++;
}

for (int i = 1; i < count.length; i++) {
    if (count[i] >= 2) {
        System.out.println(i + "는 중복입니다.");
    }
}

출력 결과는 다음과 같습니다.

2는 중복입니다.

숫자 2가 두 번 등장했기 때문에 count[2] 값이 2가 됩니다.

---

7. 가장 많이 나온 숫자 찾기

카운팅 배열을 사용하면 가장 많이 등장한 숫자도 찾을 수 있습니다. 이런 값을 보통 최빈값이라고 합니다.

int[] numbers = {1, 3, 2, 1, 3, 1, 2};

int[] count = new int[6];

for (int i = 0; i < numbers.length; i++) {
    count[numbers[i]]++;
}

int maxCount = 0;
int maxNumber = 0;

for (int i = 1; i < count.length; i++) {
    if (count[i] > maxCount) {
        maxCount = count[i];
        maxNumber = i;
    }
}

System.out.println("가장 많이 나온 숫자: " + maxNumber);
System.out.println("등장 횟수: " + maxCount);

출력 결과는 다음과 같습니다.

가장 많이 나온 숫자: 1
등장 횟수: 3

count 배열을 순회하면서 가장 큰 등장 횟수를 찾으면 됩니다. 이때 인덱스 i가 실제 숫자를 의미합니다.

---

8. 알파벳 개수 세기

카운팅 배열은 숫자뿐 아니라 문자에도 사용할 수 있습니다. 대표적인 예가 알파벳 개수 세기입니다.

영어 소문자는 총 26개입니다. 따라서 크기가 26인 배열을 만들고, 각 알파벳의 등장 횟수를 저장할 수 있습니다.

String word = "banana";

int[] count = new int[26];

for (int i = 0; i < word.length(); i++) {
    char ch = word.charAt(i);
    count[ch - 'a']++;
}

for (int i = 0; i < count.length; i++) {
    if (count[i] > 0) {
        char alphabet = (char) ('a' + i);
        System.out.println(alphabet + ": " + count[i]);
    }
}

출력 결과는 다음과 같습니다.

a: 3
b: 1
n: 2

여기서 중요한 부분은 ch - 'a'입니다.

'a' - 'a' = 0
'b' - 'a' = 1
'c' - 'a' = 2

이렇게 문자를 숫자 인덱스로 바꿔서 카운팅 배열에 저장할 수 있습니다.

소문자 알파벳 개수는 count[ch - 'a']++ 형태로 셀 수 있습니다.

---

9. 대문자 알파벳 개수 세기

대문자 알파벳도 같은 방식으로 처리할 수 있습니다. 대문자는 'A'를 기준으로 인덱스를 계산하면 됩니다.

String word = "APPLE";

int[] count = new int[26];

for (int i = 0; i < word.length(); i++) {
    char ch = word.charAt(i);
    count[ch - 'A']++;
}

for (int i = 0; i < count.length; i++) {
    if (count[i] > 0) {
        char alphabet = (char) ('A' + i);
        System.out.println(alphabet + ": " + count[i]);
    }
}

출력 결과는 다음과 같습니다.

A: 1
E: 1
L: 1
P: 2

소문자는 'a', 대문자는 'A'를 기준으로 계산한다는 점만 구분하면 됩니다.

---

10. 카운팅 배열을 사용할 수 있는 조건

카운팅 배열은 매우 편리하지만 항상 사용할 수 있는 것은 아닙니다. 값의 범위가 너무 크면 배열을 만들기 어렵기 때문입니다.

예를 들어 숫자가 1부터 100까지라면 count 배열을 만들기 쉽습니다. 하지만 숫자가 1부터 1,000,000,000까지라면 그만큼 큰 배열을 만들기 어렵습니다.

값의 범위	카운팅 배열 사용
1 ~ 100	적합
1 ~ 10,000	상황에 따라 가능
1 ~ 1,000,000,000	부적합

값의 범위가 작고 명확할 때 카운팅 배열이 특히 유용합니다. 값의 범위가 너무 크거나 음수가 섞여 있다면 HashMap 같은 자료구조를 고려하는 것이 좋습니다.

카운팅 배열은 값의 범위가 작고 정해져 있을 때 강력합니다.

---

11. 음수가 있는 경우는 어떻게 할까요?

카운팅 배열은 값을 인덱스로 사용합니다. 그런데 배열 인덱스는 음수가 될 수 없습니다.

count[-1] // 사용할 수 없음

그래서 음수가 있는 경우에는 기준값을 더해서 인덱스를 양수로 바꾸는 방식이 필요합니다. 예를 들어 값의 범위가 -5부터 5까지라면 5를 더해서 0부터 10까지로 바꿀 수 있습니다.

int[] numbers = {-2, -1, 0, 1, 2, -1};

int offset = 5;
int[] count = new int[11];

for (int i = 0; i < numbers.length; i++) {
    count[numbers[i] + offset]++;
}

System.out.println("-1의 개수: " + count[-1 + offset]);

출력 결과는 다음과 같습니다.

-1의 개수: 2

음수를 다룰 때는 값을 그대로 인덱스로 사용하지 않고, 일정한 값을 더해서 인덱스를 맞춰야 합니다.

---

12. 카운팅 배열의 시간복잡도

카운팅 배열은 입력 배열을 한 번 순회하면서 등장 횟수를 기록합니다. 따라서 입력 개수를 N이라고 하면 기본 시간복잡도는 O(N)입니다.

for (int i = 0; i < numbers.length; i++) {
    count[numbers[i]]++;
}

이 반복문은 numbers 배열의 길이만큼 실행됩니다. 따라서 시간복잡도는 O(N)입니다.

이후 count 배열을 다시 확인한다면 값의 범위만큼 추가 반복이 필요합니다. 값의 범위를 K라고 하면 전체 시간복잡도는 O(N + K)로 볼 수 있습니다.

구분	시간복잡도
입력 값 세기	O(N)
count 배열 확인	O(K)
전체	O(N + K)

K가 작다면 매우 효율적인 방식입니다.

---

13. 카운팅 배열에서 자주 하는 실수

카운팅 배열을 사용할 때는 아래 실수를 조심해야 합니다.

• count 배열의 크기를 너무 작게 만드는 경우
• 값의 범위를 확인하지 않고 배열을 만드는 경우
• 인덱스 0을 사용할지 말지 헷갈리는 경우
• 음수를 그대로 인덱스로 사용하려는 경우
• 알파벳 카운팅에서 'a' 또는 'A'를 빼지 않는 경우
• 가장 많이 나온 값을 찾을 때 count 값과 실제 숫자를 혼동하는 경우

특히 배열 크기는 항상 최댓값보다 1 크게 잡아야 안전합니다.

값의 범위가 0 ~ 5라면 → int[] count = new int[6]
값의 범위가 1 ~ 5라면 → int[] count = new int[6]

카운팅 배열의 크기는 사용할 수 있는 가장 큰 인덱스를 기준으로 정해야 합니다.

---

14. 정리

이번 글에서는 카운팅 배열에 대해 정리했습니다.

• 카운팅 배열은 값의 등장 횟수를 저장하는 배열이다.
• 값을 배열의 인덱스로 사용해 count[값]을 증가시킨다.
• 특정 값의 등장 횟수를 빠르게 확인할 수 있다.
• 중복 확인, 최빈값 찾기, 알파벳 개수 세기에 자주 사용된다.
• 소문자는 ch - 'a', 대문자는 ch - 'A'를 이용해 인덱스로 바꿀 수 있다.
• 값의 범위가 작고 명확할 때 카운팅 배열이 적합하다.
• 값의 범위가 너무 크거나 음수가 복잡하게 섞여 있으면 HashMap을 고려할 수 있다.

카운팅 배열은 알고리즘 기초 구현에서 정말 중요한 패턴입니다. 값의 범위만 잘 확인하면, 등장 횟수를 매우 빠르고 단순하게 처리할 수 있습니다.

카운팅 배열의 핵심은 값을 인덱스로 바꾸고, 등장할 때마다 해당 위치를 1씩 증가시키는 것입니다.

---

다음 글 예고

다음 글에서는 빈도수 계산에 대해 알아보겠습니다.

카운팅 배열과 HashMap을 이용해 데이터가 몇 번 등장했는지 계산하고, 가장 많이 나온 값이나 중복 여부를 판단하는 방법을 정리해보겠습니다.