문제 개요
영문자와 숫자가 섞여 있는 문자열 s가 주어졌다고 가정해 봅시다. 우리가 해야 할 일은 이 문자열에 포함된 각 숫자(0~9)가 몇 번씩 등장하는지 그 빈도를 계산하여 출력하는 것입니다.
이 문제는 크기가 10인 정수 배열 하나만으로 간단하게 해결할 수 있습니다. 배열의 각 인덱스는 숫자 0부터 9에 대응하며, 초기값은 모두 0으로 설정합니다. 이후 문자열을 한 글자씩 훑으면서 숫자를 만날 때마다 해당 인덱스의 값을 1씩 증가시키면 됩니다. 마지막으로 배열 전체를 확인해 빈도가 0보다 큰 숫자들만 출력하면 완성입니다.
예시
입력이 다음과 같다고 해보겠습니다.
s = "we85abc586wow236h69"
그렇다면 출력 결과는 아래와 같습니다.
(Number 2, Freq 1)
(Number 3, Freq 1)
(Number 5, Freq 2)
(Number 6, Freq 3)
(Number 8, Freq 2)
(Number 9, Freq 1)
풀이 접근 방법
이 문제는 다음 단계를 따라 해결할 수 있습니다.
- 크기가 10인 배열 freq를 선언하고 모든 요소를 0으로 초기화합니다.
- 인덱스 i를 0부터 문자열 길이까지 증가시키며 반복합니다.
- 현재 문자 s[i]가 숫자라면, freq[s[i] - '0'] 값을 1 증가시킵니다.
- 인덱스 i를 0부터 9까지 증가시키며 반복합니다.
- freq[i]가 0보다 크면 (숫자 i, 빈도 freq[i]) 형태로 출력합니다.
여기서 핵심은 s[i] - '0' 연산입니다. 문자 '0'의 ASCII 코드 값(48)을 기준으로 차이를 계산하면, 문자형 숫자를 실제 정수 인덱스로 변환할 수 있습니다. 예를 들어 문자 '5'는 '0'과의 차이가 5이므로 freq[5]에 기록됩니다.
C 언어 구현 예제
아래는 위 알고리즘을 C 언어로 구현한 전체 코드입니다.
#include <stdio.h>
#include <string.h>
void solve(char *s){
int freq[10] = {0};
for(int i = 0; i < strlen(s); i++){
if(s[i] >= '0' && s[i] <= '9'){
freq[s[i] - '0']++;
}
}
for(int i = 0; i < 10; i++){
if(freq[i] > 0)
printf("(Number %d, Freq %d)\n", i, freq[i]);
}
}
int main(){
char *s = "we85abc586wow236h69";
solve(s);
}
입력
"we85abc586wow236h69"
출력
(Number 2, Freq 1)
(Number 3, Freq 1)
(Number 5, Freq 2)
(Number 6, Freq 3)
(Number 8, Freq 2)
(Number 9, Freq 1)
복잡도 분석
이 알고리즘의 시간 복잡도는 O(n)입니다. 여기서 n은 문자열의 길이입니다. 문자열을 한 번만 순회하면 되고, 결과 출력은 최대 10번의 고정된 반복이므로 전체 성능에 큰 영향을 주지 않습니다. 공간 복잡도 역시 크기 10짜리 배열만 사용하므로 O(1)로 상수 수준입니다.
마무리
이처럼 카운팅 배열(counting array)을 활용하면 문자열 내 문자 빈도 문제를 매우 효율적으로 해결할 수 있습니다. 동일한 원리는 알파벳 빈도 계산, 아나그램 판별 등 다양한 문자열 처리 문제에도 응용할 수 있으니 꼭 기억해 두시길 바랍니다.