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

C++로 풀어보는 혼란스러운 숫자 II(Confusing Number II)

문제 이해하기

어떤 숫자를 180도 회전했을 때 새로운 숫자가 만들어지는 경우를 생각해 보겠습니다. 0, 1, 6, 8, 9를 180도 회전하면 각각 0, 1, 9, 8, 6으로 바뀝니다. 반면 2, 3, 4, 5, 7은 회전했을 때 유효한 숫자가 되지 않습니다.

혼란스러운 숫자(confusing number)란 180도 회전했을 때 원래 값과 다른 새로운 숫자가 되는 수를 말합니다. 따라서 양의 정수 N이 주어지면, 1부터 N까지(경계값 포함) 범위 안에 있는 혼란스러운 숫자의 개수를 구해야 합니다.

예를 들어 입력이 20이라면 출력은 6입니다. 6→9, 9→6, 10→01(즉 1), 16→91, 18→81, 19→61처럼 여섯 개의 수가 회전 시 서로 다른 수로 변하기 때문입니다.

해결 전략

이 문제는 깊이 우선 탐색(DFS)으로 유효한 자릿수만 사용해 가능한 모든 수를 생성하면서, 원래 수와 회전된 수를 동시에 누적 계산해 비교하는 방식으로 효율적으로 풀 수 있습니다. 핵심 아이디어는 다음과 같습니다.

  • 새 자릿수 dig를 뒤에 붙이면 원래 수는 num * 10 + dig로 커집니다.
  • 반면 회전된 수 입장에서는 dig의 회전 값(mapping[dig])이 최상위 자릿수에 추가되므로, rotate는 mapping[dig] * digit + rotate로 갱신됩니다. 여기서 digit는 현재 자릿수 가중치(10, 100, 1000, ...)입니다.
  • 생성 과정에서 rotate != num이면 그 수는 혼란스러운 숫자이므로 카운트를 1 증가시킵니다.

알고리즘 단계

다음 순서대로 진행합니다.

  1. 매핑 정보를 저장할 맵(mapping) 하나와 유효한 자릿수 배열(valid)을 정의합니다.
  2. solve() 함수를 정의합니다. 이 함수는 num(현재까지 만든 수), rotate(회전된 수), digit(자릿수 가중치), N(상한값)을 인자로 받습니다.
  3. rotate가 num과 같지 않으면 ret(정답 카운터)를 1 증가시킵니다.
  4. i를 0부터 valid 배열의 크기 미만까지 1씩 증가시키며 반복합니다.
    • dig := valid[i]
    • 만약 num * 10 + dig > N이면 반복문을 빠져나갑니다.
    • solve(num * 10 + dig, mapping[dig] * digit + rotate, digit * 10, N)을 재귀 호출합니다.

메인 메서드 처리 흐름

  • ret := 0으로 초기화합니다.
  • valid := { 0, 1, 6, 8, 9 }
  • mapping[0] := 0, mapping[1] := 1, mapping[6] := 9, mapping[9] := 6, mapping[8] := 8로 설정합니다.
  • 맨 앞자리가 0이 될 수 없으므로 0을 제외한 네 가지 시작점에 대해 solve(1, 1, 10, N), solve(6, 9, 10, N), solve(9, 6, 10, N), solve(8, 8, 10, N)을 호출합니다.
  • ret을 반환합니다.

C++ 구현 예제

아래 구현을 통해 더 잘 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
   public:
   int ret;
   map <int, int> mapping;
   vector <int> valid;
   void solve(lli num, lli rotate, lli digit, lli N){
      if (rotate != num) {
         ret++;
      }
      for (int i = 0; i < valid.size(); i++) {
         int dig = valid[i];
         if (num * 10 + dig > N) {
            break;
         }
         solve(num * 10 + dig, mapping[dig] * digit + rotate, digit * 10, N);
      }
   }
   int confusingNumberII(int N) {
      ret = 0;
      valid = { 0, 1, 6, 8, 9 };
      mapping[0] = 0;
      mapping[1] = 1;
      mapping[6] = 9;
      mapping[9] = 6;
      mapping[8] = 8;
      solve(1, 1, 10, N);
      solve(6, 9, 10, N);
      solve(9, 6, 10, N);
      solve(8, 8, 10, N);
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.confusingNumberII(20));
}

입력

20

출력

6

복잡도 분석

N의 자릿수를 d라고 하면, DFS가 탐색하는 노드의 수는 최대 5^d이므로 시간 복잡도는 O(5^d)입니다. 공간 복잡도는 재귀 호출 스택의 깊이에 비례하여 O(d)입니다.