プログラマー-ココア2020/ロックとキー

ロックとキー(2021、07.20)ロック

質問と回答アドレス

Programmers
Git Solution

問題の説明

考古学者の「救命圏」は古代遺跡で秘密の扉を発見し、宝物や遺跡がたくさんあると推測した.ドアを開けてみると、ドアが特殊な形の鍵でロックされていて、ドアの前に紙があり、特殊な形の鍵でロックを解除する方法が書かれています.
ロックされたロックは、メッシュサイズが1 x 1のN x Nサイズの正方形メッシュであり、特殊な形状のキーはM x Mサイズの正方形メッシュである.
鍵には溝があり、鍵にも溝と突起があります.鍵は回転と移動が可能な構造で、鍵の回転部分が鍵の溝部分とぴったり合っていると鍵が開きます.ロック領域以外の鍵の溝と突起はロック解除に影響しないが、ロック領域内では鍵の突起とロックの溝が完全に一致し、鍵の突起とロックの突起にぶつかることができない必要がある.また、ロックのすべての溝を埋めなければなりません.そうすれば、ロックを解除できます.
パラメータにキーを表す2 D配列キーとロックを表す2 D配列ロックが与えられた場合、true(キーがロックを解除できる場合)とfalse(ロックを解除できない場合)を返すソルバを完了します.
せいげんじょうけん

結合はMxM(3≦M≦20,Mは自然数)サイズの二次元配列である.

ロックは、NxN(3≦N≦20、Nは自然数)サイズの2次元配列である.

Mは常にNより小さい.

キーとlockの要素は0または1で構成されます.

0は「主」部分、1は「回転」部分を表します.

keylockresult[[0, 0, 0], [1, 0, 0], [0, 1, 1]][[1, 1, 1], [1, 1, 0], [1, 0, 1]]true

トラブルシューティング

ソリューションの推測

問題を見て理解すると、탐색に関する問題だと感じることができますが、「うん?最後にtrue/falseが正しいか間違っているかをチェックするだけでいいので、図案値で比較すると便利でしょうか?やったことがある.しかし,クレイジーな例外,テストケースの失敗,結果値をチェックするとtrue/falseのため,誤ったテストケースを明確に知ることができない.実施形態を一般的な方法と異なるようにしようとすると、グーグルはまったく助けられない.最初は問題をやめようと思ったが、学習グループの雑夫(ありがとう)から可能だと聞いて、今すぐ問題を解決した.

≪イベント｜Events｜ldap≫

アレイのインデックスマッチングを試みたが、関連事項は確認されなかった.

図に示すように、lockおよびkeyのモードが図と同時に11 인덱스を基準としてモードが作成されると、計算式は14 인덱스の位置値を変更する.式自体は問題ありません(元の式も間違っていました)が、この場合は希望のパターン値を生成できないことに気づきました.

トラブルシューティング

lock配列のサイズを仮想配列に設定すると、ホットスポットケースのように値を超えません!
最初に価格が超えられない状況を作ればいいです.(その後、答えを見て、多くの人が範囲を広げました)
では、私たちはそれをどこまで拡張すればいいのでしょうか.以下の基準が定められている.

鍵アレイの最大サイズはロックアレイのサイズであるため、鍵アレイとロックアレイが同じであれば最大値である.

ロックアレイの末尾インデックスでは、パターンを検索する必要がある場合があるため、最大値は3倍です.

3倍の場合、ロックアレイの実際の値は常に中央にある必要があります.

次の条件を満たすと、対応する画像が表示されます.

終端に一致する番号があっても、パターンは絶対に形を変えません.(重複線を使用する必要があるため、仮想範囲値をN*3-1に設定できます)
インデックスを作成するコードは次のとおりです.

/*
        virtualArr               virtualRealLockList
        1 1 1 1 1 1 1 1 1 
        1 1 1 1 1 1 1 1 1 
        1 1 1 1 1 1 1 1 1 
        1 1 1 1 1 1 1 1 1              30 31 32
        1 1 1 1 1 0 1 1 1              39 40 41
        1 1 1 1 0 1 1 1 1              48 49 50
        1 1 1 1 1 1 1 1 1 
        1 1 1 1 1 1 1 1 1 
        1 1 1 1 1 1 1 1 1
*/
public void setVirtualLock(int[][] lock){
    // 자물쇠의 크기를 확장하는데 자물쇠의 크기와 키의 크기가 같을 경우, 앞뒤로 키의 배열이 올 수 있으므로 총 3배
    // 실제 크기
    int length = lock.length;
    // 관련 변수 초기화
    virtualArr = new int[length*3][length*3];
    virtualRealLockList = new ArrayList<>();

    // 가상 배열 적용 loop
    int count = 0;
    for(int i = 0; i < virtualArr.length; i++){
        for(int j = 0; j < virtualArr.length; j++){
            // 가상 배열 범위중, 실제 lock 배열의 값을 가운데에다가 설정
            // 조건은 (0,0) ~ (length-1, length-1)이 만들어지는 실제 범위 이므로 (length, length) ~ (length * 2 -1, length * 2 -1)로 변환한다.
            if(i >= length && j >= length && i <= (length * 2) -1 && j <= (length * 2) -1){
                virtualArr[i][j] = lock[i-length][j-length];
                virtualRealLockList.add(count);
            }else{
                virtualArr[i][j] = 1;
            }
            count++;
        }
    }
}

数式の作成-ループ

配列の値を回転させるには、次の数式を使用します.
N*(N行番号)-(N列番号)
int locationValue = size * (size - row) - (size - column);
まず2 D配列を1 D配列に平らにし、loopでlocationValue変数の値を検索し、[0][0]から塗り直します.
コードは次のとおりです.

public int[][] rotation(int[][] arr){
    // 2차원 배열을 1차원 배열로 변환한다.
    int[] flatArr = Arrays.stream(arr).flatMapToInt(Arrays::stream).toArray();

    // loop 관련 변수
    int size = arr.length;
    int column = 0;
    int row = 0;

    // 임시 1차원 배열
    int[] tempArr = new int[size * size];
    for(int idx = 0; idx < flatArr.length; idx++){
        // 로테이션 위치값 - 공식에 의한 인덱스값을 찾는다.
        //N * (N - 0) - (N - 1)|N * (N - 1) - (N - 1)|N * (N - 2) - (N - 1)
        //N * (N - 0) - (N - 2)|N * (N - 1) - (N - 2)|N * (N - 2) - (N - 2)
        //N * (N - 0) - (N - 3)|N * (N - 1) - (N - 3)|N * (N - 2) - (N - 3)
        int locationValue = size * (size - row) - (size - column);
        // 인덱스값을 1차원으로 펼친 flatArr에서 값을 임시 1차원 배열에 할당한다.
        tempArr[idx] = flatArr[locationValue];
        if( row == (size - 1)){
            row = 0;
            column++;
        }else{
            row++;
        }
    }

    // 1차원 temp 배열을 2차원 result 배열로 변환
    int[][] result = new int[size][size];
    row = 0;
    column = 0;
    for (int value : tempArr) {
        result[column][row] = value;
        if ((size - 1) == row) {
            row = 0;
            column++;
        } else {
            row++;
        }
    }
    return result;
}

数式の作成-配列値の検索

パターンを探すために、次の式が適用されます.
(lock基点-key基点)+keyvalue+(lock size-keysize)*(keyvalue/keysize)-key標準列)
非常に複雑なため、コードには変数が適用されます.正直、こんな公式を作るとは思わなかった.長い間、アクセルを消してテストして挫折しました.もちろん、実際のコードテストを見たら、すぐに落ちます.
コードは以下の通りです(困難なため、各変数にコメントが詳しく書かれています.)
目標は次のとおりです.

キーとlockの配列値が変化してもパターンの形状は変化しない.

インデックスの番号付け値は完全に一致する必要があるため、ロック配列の1つの位置がキー配列の1つの位置と一致したときに生成されるモード値を比較します.

フィルタリングにより、ロックモードとキーモードのサイズが同じであり、格納されたデータが同じであればtrueが返される.

/*
    lock의 41번 인덱스가 key의 3인것으로 가정하고 패턴을 만들었을 경우
    standardPoint  38 | 38 | 38
    basePoint      41 | 45 | 46
    plusPoint       0 |  6 |  6
    newPoint       41 | 51 | 52
*/
// 변환된 lock 배열의 특정 위치에서 key의 패턴을 만드는 메소드
private List<Integer> findPattern(List<Integer> keyList, int standardLockNo, int idx){
    List<Integer> resultList = new ArrayList<>();
    // lock 패턴의 기준점 계산, key 패턴이 loop하면서 해당 값이 loop 패턴의 값이 되도록 하기 위해
    int standardPoint = standardLockNo - keyList.get(idx);
    // key 패턴의 값이 key 배열의 몇번째 row에 있는지 계산하기 위해
    int standardRow = keyList.get(idx) / keyLength;
    // key 패턴 loop
    for(int keyNo : keyList){
        // 기본값, 각 기준에 해당하는 key 패턴은 해당 lock 패턴의 값과 일치하게 나와야 한다.
        int basePoint = keyNo + standardPoint;
        // lockLength - keyLength -> 배열 크기가 다른 lock과 key배열의 차이
        // (keyNo / keyLength) - standardRow -> key 패턴의 값이 실제 어느 열에 존재하는지
        // lock 패턴과 key 패턴의 크기가 다를때, 같은 패턴의 모양을 만들어주기 위해 크기가 차이나는 만큼 인덱스 값을 더해서 만든다.
        int plusPoint = (lockLength - keyLength) * ((keyNo / keyLength) - standardRow);
        // basePoint와 plusPoint의 합으로 최종적인 virtual lock pattern의 위치 값을 찾는다.
        int newPoint = basePoint + plusPoint;

        // 필터링 - 확장되었지만 실제로는 확정 전의 lock 패턴에 값이 존재하는 key의 값만이 대상이 되므로
        // 해당 범위가 아닌 point값은 lock의 실제범위를 벗어나는 값이다.
        if(virtualRealLockList.contains(newPoint)){
            resultList.add(newPoint);
        }
    }
    return resultList;
}

// 최종적으로 필터링 이후 만들어진 두 패턴을 비교하는 메소드
private boolean diffList(List<Integer> keyList, List<Integer> lockList){
    // 실제 범위이외의 데이터는 필터링 처리 되었기 때문에 두 리스트의 사이즈는 같으며 포함되어야 한다.
    // 단순 contains 사용시, 패턴에서 자물쇠와 키가 둘다 1인 케이스가 있어서 테스트 케이스 3개가 실패한다.
    // 참고) 실제 정답에서는 XOR처리라고 되어있다.
    if(keyList.size() == lockList.size()){
        return lockList.containsAll(keyList);
    }
    return false;
}

テスト結果

試験番号合格か否かメモリと時間試験番号合格か否かメモリと時間試験番号合格か否か(3.27 ms,52.7 MB)試験20合格(116.46 ms,58.8 MB)試験2合格(0.11 ms,52.1 MB)試験21合格(8.61 ms,54.3 MB)試験3合格(24.22 ms,54.9 MB)試験22合格(90.99 ms,67.5 MB)試験4合格(0.11 ms,54 MB)試験23合格(798.ms,52.8 MB)試験5合格(42.27 ms,56.9 MB)試験24合格(15.76 ms,52.5 MB)試験6合格(23.67 ms,52.5 MB)試験25合格(56.86 ms,56.6 MB)試験7合格(2.50 ms,52.2 MB)試験26合格(279.80 ms,71.3 MB)試験8合格(68.75 ms,56.8 MB)試験27合格(1932.11 ms,200 MB)試験9合格(184.03 ms,71.7 MB)試験28合格(28.92 ms,55.1 MB)試験10合格(75.6 MB)試験10合格試験11合格(144.206 ms,141 MB)試験30合格(60.21 ms,58.6 MB)試験12合格(0.08 ms,52.6 MB)試験31合格試験35合格(10.97 ms,52.6 MB)試験17合格(14.17 ms,52.7 MB)試験36合格(17.22 ms,53 MB)試験18合格(24.64 ms,52.8 MB)試験37合格(13.21 ms,52.6 MB)試験19合格(4.12 ms,52.6 MB)試験38合格(10.40 ms,52.8 MB)

伝統的な解題方式

lockの配列とkeyの配列を重ねるだけで、lock配列のすべての要素が1であるかどうかを確認できます.重なる部分は図のように2 X 2を掴むのではなく、重なる部分は1 X 1で、左上から1 X 1、2 X 2です.残りの配列を1つの配列で検索してチェックすればいいです.3回の解題方法を見て、私の解題方法がどれだけ難しいか知った.(公式を作成しました…)
さらに,この方法では,ロックと鍵配列の大きさの違いを知る必要はない.ナビゲーションだけで済むし、重要なのはlock配列とkey配列の値がすべて1であるため、鍵がロックを通過できない場合になるので、0に変換したりfalseに戻ったりすることができます.

ポスト

長い時間がかかり、多くの失敗で挫折した.次に問題を見て、どのような方法で解決するかを確認し、実施する考えです.サンプル問題ではすべてのテスト・インスタンスをチェックできないため、実際にテスト・インスタンスが正しく実装されても、多くの失敗が発生します.今は勉強のために、時間をかけて解答していますが、実際には決められた時間内に解答しなければならないので、このように一人で別の方向に行かないでください.