모바일 숫자 키패드 문제

난이도 하드
자주 묻는 질문 아마존 MAQ Microsoft 스프링클러
조합 동적 프로그래밍 매트릭스 조회수 52

문제 정책

모바일 숫자 키패드 문제에서 우리는 숫자 키패드를 고려합니다. 현재 버튼의 위, 아래, 왼쪽 및 오른쪽에있는 버튼 만 누를 수 있도록 주어진 길이의 가능한 모든 숫자 시퀀스를 찾아야합니다. 아래 이미지에서 회색으로 표시된 하단 행 모서리 버튼 (* (별표) 및 # (해시))을 누를 수 없습니다.

숫자 키패드

1
10

설명 : 모든 숫자 (0 ~ 9)를 사용할 수 있으므로 답에 10이 기여합니다.

2
36

설명 : 0을 선택한 경우 두 번째 숫자로 0과 8을 선택할 수 있습니다.

1을 선택한 다음 두 번째 숫자로 1, 2, 4를 선택할 수 있습니다. 마찬가지로 모든 숫자에 대해이 작업을 수행합니다.

 

모바일 숫자 키패드 문제에 대한 대처

재귀 적 접근

모바일 숫자 키패드 문제의 경우 가장 먼저 떠오르는 것은 재귀 적 접근 방식입니다. 그래서 우리는 문제를 해결할 수 있습니다 재귀 적으로 그래서 우리가 i, j 위치에 있고 n 개의 숫자를 선택할 수 있다면 위쪽 방향 (i-1, j), 아래쪽 방향 (i + 1, j), 왼쪽 방향 (i, j-1)으로 이동할 수 있습니다. ), 오른쪽 방향 (i, j + 1), 현재 위치 (i, j)에서 n-1 개의 숫자 중에서 선택할 수 있습니다. 이 접근 방식은 절대적으로 옳지 만 충분히 효율적이지 않습니다.

//Base Case
if (N = 1) return 10
else
    return sum of all findNumberOfSequences(i, j, n) where i,j is new position after a valid move from current position

동적 프로그래밍

n과 같은 숫자 시퀀스의 길이에 대한 모바일 숫자 키패드 문제를 풀려고 할 때. 초기 문제가 더 작은 하위 문제에 의존한다는 것을 알 수 있습니다. n이 3 일 때 문제를 생각해보십시오. 그러면 문제가 2와 같은 길이의 시퀀스 수에 의존한다는 것을 알 수 있습니다. 그런 다음 위쪽 방향으로 아래쪽 방향 왼쪽 방향과 오른쪽 방향으로 이동하거나 같은 자리이지만 우리가이 자리 (숫자)를 취하고 답을 추가했기 때문에. 문제는 n = 2 인 작은 문제로 축소되었습니다. 이제 우리가 숫자에서 시작하여 허용 된 방향으로 이동했음을 알 수 있다면 하위 문제가 겹치는 것을 볼 수 있습니다. 동적 프로그래밍.

일반적으로 동적 프로그래밍, 우리가하는 일은 먼저 작은 문제를 해결 한 다음 더 작은 문제의 결과를 결합하여 초기 문제를 해결하여 n이 1이고 n이 2와 같은 식으로 해결됩니다.

암호

C ++ 코드

#include <bits/stdc++.h> 
using namespace std;

int findNumberOfSequences(int n) 
{ 
  char keypad[4][3] = {{'1','2','3'}, 
                       {'4','5','6'}, 
                       {'7','8','9'}, 
                       {'*','0','#'}};
  
  //Base Case
  if(n <= 0) 
    return 0; 
  if(n == 1) 
    return 10; 

  //Directions to move to
  int dir[][2]= {{0,0}, {0,-1}, {-1,0}, {0,1}, {1,0}};

  //dp[i][j] = number of sequences of length j starting with digit i
  int dp[10][n+1];
  memset(dp,0, sizeof dp);
  
  // fill the numbers starting with digit i and of length 1 
  for(int i=0; i<=9; i++)
    dp[i][1] = 1;

  // Now solve problem for n=2,3,.. using smaller sub-problems
  for(int sizeOfSequence=2; sizeOfSequence<=n; sizeOfSequence++)
  { 
    for(int row=0; row<4; row++)
    { 
      for (int col=0; col<3; col++)
      { 
        if (keypad[row][col] != '*' && keypad[row][col] != '#') 
        { 
          //fixing the first digit
          int num = keypad[row][col] - '0';

          //Now select the remaining digit in sequence
          for(int step=0; step<5; step++) 
          { 
            int new_row = row + dir[step][0]; 
            int new_col = col + dir[step][1]; 
            if(new_row>=0 && new_row<4 && new_col>=0 && new_col<3
            && keypad[new_row][new_col]!='*' && keypad[new_row][new_col]!='#') 
            { 
              int nextNum = keypad[new_row][new_col] - '0'; 
              dp[num][sizeOfSequence] += dp[nextNum][sizeOfSequence-1]; 
            } 
          } 
        } 
      } 
    } 
  } 

  // Add the number of sequences of length starting with digit i(0 to 9)
  int ans = 0; 
  for(int i=0; i<=9; i++) 
    ans += dp[i][n]; 
  return ans; 
} 

int main() 
{ 
  int t;cin>>t;
  while(t--){
    int n;cin>>n;
    cout<<"Number of sequences of length "<<n<<" = "<<findNumberOfSequences(n)<<endl;
  }
} 
5
1
2
3
4
5
Number of sequences of length 1 = 10
Number of sequences of length 2 = 36 
Number of sequences of length 3 = 138 
Number of sequences of length 4 = 532 
Number of sequences of length 5 = 2062

 

자바 코드

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    
    static int findNumberOfSequences(int n) 
    { 
      	char keypad[][] = {{'1','2','3'}, 
    		           {'4','5','6'}, 
    	         	   {'7','8','9'}, 
    			   {'*','0','#'}};
      
      	//Base Case
    	if(n <= 0) 
    		return 0; 
    	if(n == 1) 
    		return 10; 
    
    	//Directions to move to
    	int dir[][]= {{0,0}, {0,-1}, {-1,0}, {0,1}, {1,0}};
    
    	//dp[i][j] = number of sequences of length j starting with digit i
    	int dp[][] = new int[10][n+1];
        
        for(int i=0;i<10;i++)
            for(int j=0;j<n+1;j++)
                dp[i][j]= 0;
                
    	// fill the numbers starting with digit i and of length 1 
    	for(int i=0; i<=9; i++)
    		dp[i][1] = 1;
    
    	// Now solve problem for n=2,3,.. using smaller sub-problems
    	for(int sizeOfSequence=2; sizeOfSequence<=n; sizeOfSequence++)
    	{ 
    		for(int row=0; row<4; row++)
    		{ 
    			for (int col=0; col<3; col++)
    			{ 
    				if (keypad[row][col] != '*' && keypad[row][col] != '#') 
    				{ 
    					//fixing the first digit
    					int num = keypad[row][col] - '0';
    
    					//Now select the remaining digit in sequence
    					for(int step=0; step<5; step++) 
    					{ 
    						int new_row = row + dir[step][0]; 
    						int new_col = col + dir[step][1]; 
    						if(new_row>=0 && new_row<4 && new_col>=0 && new_col<3
                                                && keypad[new_row][new_col]!='*' && keypad[new_row][new_col]!='#') 
    						{ 
    							int nextNum = keypad[new_row][new_col] - '0'; 
    							dp[num][sizeOfSequence] += dp[nextNum][sizeOfSequence-1]; 
    						} 
    					} 
    				} 
    			} 
    		} 
    	} 
    
      	// Add the number of sequences of length starting with digit i(0 to 9)
    	int ans = 0; 
    	for(int i=0; i<=9; i++) 
    		ans += dp[i][n]; 
    	return ans; 
    } 

    public static void main(String[] args) 
    { 
        
    	Scanner sc = new Scanner(System.in); 
    	int t = sc.nextInt(); 
    	while(t-- > 0){ 
            int n = sc.nextInt();
            int ans = findNumberOfSequences(n);
    	    System.out.println("Number of sequences of length "+n+" = "+ans);
    	}
    } 
}
5
1
2
3
4
5
Number of sequences of length 1 = 10
Number of sequences of length 2 = 36
Number of sequences of length 3 = 138
Number of sequences of length 4 = 532
Number of sequences of length 5 = 2062

복잡성 분석

시간 복잡성: 모바일 숫자 키패드 문제의 경우 O (n)

많은 중첩 루프를 사용했지만 일정한 시간에 실행되는 것으로 간주하므로 외부 루프 때문에 선형 시간 복잡성 O (n)이 있습니다.

공간 복잡성: 모바일 숫자 키패드 문제의 경우 O (n)

크기가 n 인 1 차원 DP 배열이 있기 때문입니다. 우리는 O (n)의 선형 공간 복잡도를 가지고 있습니다.

Translate »