이 문제에서는 하나의 매우 큰 숫자가 주어지며, 그 안에서 반복해서 나타나는 모든 3자리 숫자를 찾아 출력해야 합니다.
문제 이해하기
먼저 예시를 통해 문제를 살펴보겠습니다.
입력: 98769876598765
출력:
987: 3번
876: 3번
765: 2번
위 예시에서 숫자 "98769876598765" 안에는 "987"과 "876"이 각각 3번, "765"가 2번 등장하는 것을 확인할 수 있습니다.
해결 접근 방법
매우 큰 숫자는 일반적인 정수 자료형(int, long long 등)에 담을 수 없기 때문에 문자열(string) 형태로 저장합니다. 문자열의 각 문자는 숫자의 한 자릿수를 의미합니다.
해결 과정은 다음과 같습니다.
- 문자열의 처음 세 문자를 이용해 첫 번째 3자리 숫자를 만들고 맵(map)에 저장합니다.
- 인덱스 3부터 문자열 끝까지 순회하면서, 기존 값에서 백의 자리와 십의 자리를 남기고(나머지 연산 활용) 새 문자를 붙여 다음 3자리 숫자를 구합니다. 이는 슬라이딩 윈도우 기법입니다.
- 각 3자리 숫자의 등장 빈도를 맵에 기록합니다.
- 마지막으로 빈도가 1보다 큰, 즉 두 번 이상 등장한 3자리 숫자만 출력합니다.
구현 코드
아래 코드는 위에서 설명한 해결 방법을 구현한 것입니다.
#include <bits/stdc++.h>
using namespace std;
void printRepeatingNumber(string s) {
int i = 0, j = 0, val = 0;
map <int, int> threeDigitNumber;
val = (s[0] - '0') * 100 + (s[1] - '0') * 10 + (s[2] - '0');
threeDigitNumber[val] = 1;
for (i = 3; i < s.length(); i++) {
val = (val % 100) * 10 + s[i] - '0';
if (threeDigitNumber.find(val) != threeDigitNumber.end()) {
threeDigitNumber[val] = threeDigitNumber[val] + 1;
} else {
threeDigitNumber[val] = 1;
}
}
for (auto number : threeDigitNumber) {
int key = number.first;
int value = number.second;
if (value > 1)
cout<<key<<": "<<value<<" times\n";
}
}
int main() {
string num = "98769876598765";
cout<<"All 3 digit repreating numbers are :\n";
printRepeatingNumber(num);
}
실행 결과
All 3 digit repeating numbers are −
765: 2 times
876: 3 times
987: 3 times
동작 원리 설명
핵심은 (val % 100) * 10 + s[i] - '0' 부분입니다. 현재 3자리 값에서 앞의 백의 자리를 제거하고(val % 100) 10을 곱해 한 자리를 밀어낸 뒤, 새로운 문자를 숫자로 변환해 더함으로써 다음 3자리 숫자를 효율적으로 계산합니다.
또한 map<int, int>을 사용하기 때문에 결과가 키 값 기준으로 오름차순 정렬되어 출력됩니다. 전체 시간 복잡도는 O(N)으로, 문자열 길이에 비례하여 선형적으로 처리되므로 아주 큰 숫자에도 효율적으로 동작합니다.