[アルゴリズム解答]プログラマーが写真を撮る

昨日解答した時に急に何かあって終わりませんでした今日で終わりです~
プログラマーの中で解けるレベル2の2017 Kakao Code公式出題に照準を合わせるです!最近、ある企業家の珂太が似たようなタイプの問題を出して、その時この問題を考えて解答しましたが、今日はその問題を考えて解答しました.

問題の説明

秋になって、Kakaofriendsグループでハイキングに行きました.楽しい時間を過ごすために、最後に集合写真を撮って、カメラの前に一列に並んだ.しかし、誰もが望む構成が異なり、どの順番で設定するかを決めるのに時間がかかります.ニオはフロドと並んで立っていて、パイプに火をつけられたライアンはパイプから少なくとも3つ離れていることを望んでいる.写真を撮って帰る途中、武智はみんなの要求を満たす方法があるのではないかと考えた.すべての友人が自分の希望する条件を入力として受け取り、すべての条件が満たされている場合は、数字を計算するプログラムを作成します.

入力フォーマット

条件個数を表す整数nとn個の要素からなる文字列配列データを入力して与えます.Dataの要素は、friendsごとに必要な条件N~F=0などの文字列から構成される.制限条件は以下の通りです.

1 <= n <= 100

dataの要素は、5文字からなる文字列です.各要素の条件は次のとおりです.

の最初の文字と3番目の文字は以下の8つの1つです.{A、C、F、J、M、N、R、T}はそれぞれピッチ、CON、PRODO、JI、MOZY、ニオ、ライアン、救命輪を表す.最初の字は条件を出した友達で、3番目の字は相手です.最初の字と3番目の字はいつも違います.

第二文字はいつも~.

の4番目の字は以下の3つの1つです.{=、<、>}は、それぞれ同じ、小さい、または超えを表す.

の5文字目は0以上6以下の整数の文字型で、条件で与えられた間隔を表す.このとき、間隔は2つのfriends間の別のfriendsの数である.

出力フォーマット

すべての条件を満たす数を返します.

I/O例

ndataanswer2["N~F=0", "R~T>2"]36482["M~C<2", "C~M>1"]0

解答方法

答え方は簡単!私は探索で解決したから~
まず、8人のキャラクターを1行に並べた全ての場合の数字を求める.これはソートで得られます.いずれの場合もmapに<キャラクタアルファベット、位置>として保存し、各キャラクタのアルファベットで立っている位置をO(1)にインポートします.その後、条件を判別するためには、それぞれの場合の数において、キャラクタの位置をすばやく取得することが望ましい.
キューできるすべての場合の数を求めると,各場合の数が所定の条件を満たすか否かを判断する.このため,入力した条件データをグループ化し,有意義な要素を抽出した.2つのキャラクターのアルファベットと記号(>,<,=)と、また欲しい距離があるので、要素を選びました.そして地図から2つのキャラクターの位置を得て、2つのキャラクターの間の間隔を求めました!(ここでは直接車を求めることはできませんが、すぐそばにいると、質問では0を意味します.実際の計算は1!たぶん解の時にこれが一度間違っているからです)実際の距離と欲しい距離、記号を利用して条件を満たすかどうかを判断し、すべての条件を満たすと++と答えます.一つ間違えてもやってくれない.

どう見ても論理は問題ありませんが、提出すると間違った答えが出るので、問題を見た後、グローバル変数や静的変数を再定義します。本当に他の問題は一度もこんなことをしたことがありません...だから定義コードを追加して、通過しました!困った人がいたら参考にしてみるのもいいですね~

コード#コード#

import java.util.*;

class Solution {
    public static char[] mems;
    public static ArrayList<Map<Character, Integer>> target;

    public static void permutation(boolean[] visited, char[] output, int size, int depth){
        if(depth == size){
            Map<Character, Integer> temp = new HashMap<>();
            for(int i=0; i<depth; i++){
                temp.put(output[i], i);
            }
            target.add(temp);
            return;
        }
        for(int i=0; i<mems.length; i++){
            if(!visited[i]){
                output[depth] = mems[i];
                visited[i] = true;
                permutation(visited, output, size, depth+1);
                visited[i] = false;
            }
        }
    }

    public static boolean isPossible(char op, int gap, int num){
        if(op == '=') return gap == num;
        else if(op == '<') return gap < num;
        else return gap > num;
    }

    public int solution(int n, String[] data) {
        int answer = 0;

        target = new ArrayList<>();
        mems = new char[]{'A', 'C', 'F', 'J', 'M', 'N', 'R', 'T'};
        int size = mems.length;
        permutation(new boolean[size], new char[size], size, 0);

        char mem1, mem2, operand;
        int gap, num;
        boolean flag;
        for(Map<Character, Integer> elem : target){
            flag = true;
            for(String info : data){
                mem1 = info.charAt(0);
                mem2 = info.charAt(2);
                operand = info.charAt(3);
                num = info.charAt(4)-'0';
                gap = Math.abs(elem.get(mem1)-elem.get(mem2))-1;
                if(!isPossible(operand, gap, num)){
                    flag = false;
                    break;
                }
            }
            if(flag) answer++;
        }

        return answer;
    }
}