Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 구현하는 스트로보그램매틱 숫자 III — 주어진 범위 내 개수 구하기

이번 문제는 스트로보그램매틱 숫자(Strobogrammatic Number)의 총 개수를 특정 범위 [low, high] 안에서 세는 함수를 정의하는 것입니다.

스트로보그램매틱 숫자란 180도 회전했을 때 원래 모양과 똑같이 보이는 수를 말합니다. 예를 들어 69는 뒤집으면 96처럼 보이지만, 실제로 자기 자신과 같은 형태를 유지하는 대표적인 숫자 조합은 0↔0, 1↔1, 8↔8, 6↔9, 9↔6입니다.

예를 들어 입력이 low = "50", high = "100"이라면 출력은 3이 됩니다. 이 범위에 속하는 스트로보그램매틱 숫자는 69, 88, 96으로 총 세 개이기 때문입니다.

문제 해결 접근 방법

이 문제를 해결하기 위해 다음 단계를 따릅니다.

1단계: findStrobogrammatic() 함수 정의

  • n을 매개변수로 받아 길이가 n인 모든 스트로보그램매틱 숫자를 생성합니다.
  • 결과를 저장할 배열 ret을 선언합니다.

2단계: 중심 자릿수 처리

  • n이 홀수(n & 1이 참)라면 가운데 자리에 올 수 있는 숫자인 "0", "1", "8"을 ret에 추가합니다.
  • n이 짝수라면 빈 문자열("")을 ret에 추가합니다.

3단계: 대칭 자릿수 확장

  • n이 1보다 클 동안 n을 2씩 줄여가며 반복합니다.
  • 각 반복에서 임시 배열 temp를 만들고, 기존 ret의 각 문자열 s에 대해 다음을 추가합니다.
    • n > 3일 경우(즉, 맨 앞자리가 아닐 때): "0" + s + "0" 추가 — 선행 0 방지를 위한 조건입니다.
    • 항상 추가: "1" + s + "1", "8" + s + "8", "6" + s + "9", "9" + s + "6"
  • 반복이 끝나면 ret = temp로 갱신합니다.

4단계: 메인 로직에서 범위 비교

  • 결과 카운트 ret := 0으로 초기화하고 배열 v를 선언합니다.
  • i를 low의 길이부터 high의 길이까지 증가시키며 findStrobogrammatic(i)를 호출해 v를 얻습니다.
  • v의 각 요소 v[j]에 대해, 그 값이 low 이상이고 high 이하인지 문자열 크기 비교(compare 함수)로 판단한 후 조건을 만족하면 ret을 1씩 증가시킵니다.
  • 최종적으로 ret을 반환합니다.

여기서 compare(a, b) 함수는 두 문자열의 길이가 같으면 사전순으로 a ≥ b인지 확인하고, 길이가 다르면 단순히 길이 비교를 통해 a가 더 큰지 판단합니다. 숫자 문자열은 길이가 곧 크기를 의미하므로 이 방식으로 오버플로우 없이 안전하게 비교할 수 있습니다.

예제 코드

아래 C++ 구현을 통해 더 잘 이해할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    vector<string> findStrobogrammatic(int n) {
        vector<string> ret;
        if (n & 1) {
            ret.push_back("0");
            ret.push_back("1");
            ret.push_back("8");
        }
        else {
            ret.push_back("");
        }
        for (; n > 1; n -= 2) {
            vector<string> temp;
            for (int i = 0; i < ret.size(); i++) {
                string s = ret[i];
                if (n > 3) {
                    temp.push_back("0" + s + "0");
                }
                temp.push_back("1" + s + "1");
                temp.push_back("8" + s + "8");
                temp.push_back("6" + s + "9");
                temp.push_back("9" + s + "6");
            }
            ret = temp;
        }
        return ret;
    }
    bool compare(string a, string b){
        return a.size() == b.size() ? a >= b : a.size() > b.size();
    }
    int strobogrammaticInRange(string low, string high) {
        int ret = 0;
        vector<string> v;
        for (int i = low.size(); i <= high.size(); i++) {
            v = findStrobogrammatic(i);
            for (int j = 0; j < v.size(); j++) {
                ret += compare(v[j], low) && compare(high, v[j]);
            }
        }
        return ret;
    }
};
main(){
    Solution ob;
    cout <<(ob.strobogrammaticInRange("50", "100"));
}

입력

"50","100"

출력

3

정리

이 알고리즘은 중앙에서 바깥쪽으로 대칭 쌍(0-0, 1-1, 8-8, 6-9, 9-6)을 하나씩 붙여가며 스트로보그램매틱 숫자를 생성한 뒤, 문자열 비교를 통해 범위 내에 포함되는 숫자만 카운트합니다. 숫자를 직접 정수로 변환하지 않고 문자열로 처리하기 때문에 매우 큰 수의 범위에서도 오버플로우 걱정 없이 동작한다는 점이 핵심 장점입니다.