C++로 휴대폰 번호가 멋진 번호(Fancy Number)인지 확인하는 방법

10자리 휴대폰 번호가 주어졌을 때, 이 번호가 멋진 번호(Fancy Number)인지 판별하는 것이 우리의 과제입니다. 멋진 번호가 되기 위한 조건은 세 가지가 있으며, 이 중 하나라도 만족하면 해당 번호는 멋진 번호로 간주됩니다.

멋진 번호의 세 가지 조건

• 같은 숫자가 연속으로 세 번 나타나는 경우 — 예: 555
• 연속된 세 숫자가 오름차순 또는 내림차순인 경우 — 예: 123 또는 321
• 특정 숫자가 네 번 이상 나타나는 경우 — 예: 8965499259에서 숫자 9가 네 번 등장

예를 들어 9859009976은 세 번째 조건(숫자 9가 네 번 이상 등장)을 만족하므로 멋진 번호입니다.

접근 방법

번호를 문자열(string) 형태로 입력받아 처리합니다. 세 번째 조건을 검사할 때는 각 숫자의 등장 빈도를 세어야 하는데, 이때 해싱(hash)의 기본 개념인 빈도 배열(frequency array)을 활용합니다.

• consecutiveThreeSameDigits(): 같은 숫자가 연속 세 번 나오는지 확인
• incDecThree(): 연속된 세 숫자가 증가하거나 감소하는지 확인
• fourOccurrence(): 빈도 배열을 이용해 특정 숫자가 네 번 이상 나오는지 확인

C++ 구현 예제

#include <iostream>
using namespace std;

// 같은 숫자가 연속으로 세 번 나타나는지 확인
bool consecutiveThreeSameDigits(string s) {
    for (int i = 0; i < s.size() - 2; i++) {
        if (s[i] == s[i + 1] && s[i + 1] == s[i + 2])
            return true;
    }
    return false;
}

// 연속된 세 숫자가 증가 또는 감소하는지 확인
bool incDecThree(string s) {
    for (int i = 0; i < s.size() - 2; i++) {
        if ((s[i] < s[i + 1] && s[i + 1] < s[i + 2]) ||
            (s[i] > s[i + 1] && s[i + 1] > s[i + 2]))
            return true;
    }
    return false;
}

// 특정 숫자가 네 번 이상 나타나는지 확인 (해싱 활용)
bool fourOccurrence(string s) {
    int freq[10] = {0};
    for (int i = 0; i < s.size(); i++)
        freq[s[i] - '0']++;
    for (int i = 0; i < 10; i++)
        if (freq[i] >= 4)
            return true;
    return false;
}

// 세 조건 중 하나라도 만족하면 멋진 번호
bool isFancyNumber(string s) {
    if (consecutiveThreeSameDigits(s) || incDecThree(s) || fourOccurrence(s))
        return true;
    else
        return false;
}

int main() {
    string s = "7609438921";
    if (isFancyNumber(s))
        cout << "This is fancy number";
    else
        cout << "This is not a fancy number";
}

실행 결과

This is fancy number

코드 설명

예제 번호 7609438921의 경우, 앞자리의 7 → 6 → 0이 내림차순을 이루므로 두 번째 조건(incDecThree)을 만족하여 멋진 번호로 판별됩니다.

각 함수는 문자열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 빈도 배열은 크기가 10으로 고정되어 있어 공간 복잡도도 O(1)로 매우 효율적입니다. 참고로 빈도 검사 시 반복 범위를 반드시 i < 10으로 설정해야 숫자 9가 네 번 이상 등장하는 경우도 올바르게 감지할 수 있습니다.