행렬 확장을 기반으로 문제를 토론합니다. 확장 행렬은 크기가 일정한 요소만큼 지속적으로 증가하는 행렬입니다.
여기에서 크기가 2배로 확장되는 문자 행렬이 있습니다. 즉, 행렬의 원래 크기가 N * N이면 확장된 행렬의 크기는 2N * 2N이 됩니다. (i, j)에 있는 일련의 문자가 주어지고 (i, (j - N - 1)%N)에 있는 일련의 문자를 반환해야 합니다.
초기 확장 매트릭스를 시각화하여 이해합시다.
Given Matrix -> [ a, b ] [ c, d ], 2 X 2 matrix
Multiplying with { a, b, c, d }
A X [ a, b ]
B X [ a, b ]
C X [ a, b ]
D X [ a, b ]
[ c, d ] [ c, d ] [ c, d ] [ c, d ]
Expanded Matrix -> [ aa, ab, ba, bb ]
[ ac, ad, bc, bd ]
[ ca, cb, da, db ]
[ cc, cd, dc, dd ], 4X4 matrix
To expand again, multiply it by { a, b, c, d } and a matrix of size 8X8 will be formed.
Expanded Matrix - > [ aaa, aab, aba, abb, baa, bab, bba, bbb ]
[ aac, aad, abc, abd, bac, bad, bbc, bbd ]
[ aca, acb, ada, adb, bca, bcb, bda, bdb ]
[ acc, acd, adc, add, bcc, bcd, bdc, bdd ]
[ caa, cab, cba, cbb, daa, dab, dba, dbb ]
[ cac, cad, cbc, cbd, dac, dad, dbc, dbd ]
[ cca, ccb, cda, cdb, dca, dcb, dda, ddb ]
[ ccc, ccd, cdc, cdd, dcc, dcd, ddc, ddd ] 다음은 두 개의 초기 확장 행렬입니다. 따라서 "bcc" 문자 시퀀스가 주어졌다고 가정해 보겠습니다. 그러면 바로 왼쪽 시퀀스, 즉 "add"를 반환해야 합니다. 또한, 행렬은 원형이라고 가정합니다. 즉, 주어진 시퀀스가 (i, 0)에 있으면 시퀀스를 (i, N-1)에 반환합니다. 예를 들어
Input: abb Output: aba Explanation: The sequence just left to abb is aba in the 8X8 matrix. Input: aadc Output: aacd Input: abbcd Output: abbcc
해결책을 찾기 위한 접근 방식
문제를 먼저 살펴보고 마음에 떠오르는 유일한 해결책은 주어진 시퀀스를 포함하지만 그다지 복잡해 보이지 않는 확장 행렬을 찾는 것입니다. 먼저 행렬을 만든 다음 시퀀스를 검색해야 합니다.
효율적인 접근
처음에 확장된 일부 행렬을 살펴본 후 이전 요소를 볼 수 있는 패턴을 찾았습니다. 즉
-
마지막 인덱스에서 문자 시퀀스를 탐색합니다.
-
인덱싱된 요소가 'b' 또는 'd'인 경우 'a' 또는 'c'로 변경하고 배열 탐색을 중지합니다.
-
인덱싱된 요소가 'a' 또는 'c'인 경우 'b' 또는 'd'로 변경하고 다음 인덱스로 이동하여 확인합니다.
예시
위 접근 방식에 대한 C++ 코드
#include <bits/stdc++.h>
using namespace std;
int main (){
string seq = "abbcd";
int n = seq.length ();
// traverse through the string from last.
for (int i = n; i >= 0; i--){
// if the element is b or d, change them and stop traversing.
if (seq[i] == 'b'){
seq[i] = 'a';
break;
}
if (seq[i] == 'd'){
seq[i] = 'c';
break;
}
// if an element is b or d, change them and move to the next element.
if (seq[i] == 'a')
seq[i] = 'b';
else if (seq[i] == 'c')
seq[i] = 'd';
}
cout << "The Previous sequence is: " << seq;
return 0;
} 출력
The previous sequence is: abbcc
결론
이 기사에서 우리는 확장되는 문자 행렬과 그것이 어떻게 형성되는지에 대해 논의했습니다. 우리는 또한 확장 행렬에서 이전 요소를 찾는 문제에 대해 논의했습니다. 캐릭터의 행렬을 확장하여 생성된 패턴을 이해함으로써 이 문제를 해결했습니다.
또한 C, Java, Python 등과 같은 모든 프로그래밍 언어로 작성할 수 있는 이 문제에 대한 C++ 코드에 대해 논의했습니다. 이 튜토리얼이 도움이 되기를 바랍니다.