[アルゴリズム]11109公開順序アルゴリズム#シーケンス#スタックデータ
6024 ワード
📌 パブリケーション順序の取得
工場を利用して発表順を得ることです.
すべてのパケットのパブリケーション順序について、数値を順番に取得し、パブリケーション順序を説明すると、このパブリケーション順序が何回目のパブリケーションの数値であるかを答えることができます.
総グループの数Nと先生の言う発表順kを与えると、正しい戻り値を求め、金符号化に正しい答えを出させる.
番号が小さいほど、すべての場合の配列が前にあると仮定します.
ex)N=3であれば[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,1,2],[3,2]
パラメータ1:N
番号タイプ1<=N<=12のグループ数
パラメータ2:K
番号付けタイプのArray(0<=index)
ex)nが3の場合、kは[2,3,1]である.
すべての場合の数字が2次元配列に含まれる場合、[1,2,3],[1,3,2],[2,1,3],[2,3,1,3],[3,1,2],[3,2],[3,2,1,1]とすることができる.
返される値は3です.
注意事項
k内に重複する要素がないと仮定する.
I/O例 let output = orderOfPresentation(3, [2, 3, 1]);
console.log(output);//3 output = orderOfPresentation(5, [1, 3, 2, 4, 5])
console.log(output);//6 問題では、まず発表順に順番に数量を求めた後だという.これが利用工場です.まず工場補助関数を生成します.この関数は後で使用します.
2)合計エントリ数がNの場合、どのエントリがすでに含まれているかを決定する配列が生成される.
3)0番目にスタックデータでfalseを生成し,それらをすべてfalseとして埋め込む.
5)ISUsedをチェックして使用済みかどうかを確認する(重複していないため)
6)numの前に現れる数字の配列をコピーし、
7)未使用数量を求める.
8)使用されていない数、それ以前のすべての状況をカウントします.
9)orderに追加します.
リファレンス
https://lienkooky.tistory.com/77
工場を利用して発表順を得ることです.
すべてのパケットのパブリケーション順序について、数値を順番に取得し、パブリケーション順序を説明すると、このパブリケーション順序が何回目のパブリケーションの数値であるかを答えることができます.
総グループの数Nと先生の言う発表順kを与えると、正しい戻り値を求め、金符号化に正しい答えを出させる.
番号が小さいほど、すべての場合の配列が前にあると仮定します.
ex)N=3であれば[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,1,2],[3,2]
パラメータ1:N
番号タイプ1<=N<=12のグループ数
パラメータ2:K
番号付けタイプのArray(0<=index)
ex)nが3の場合、kは[2,3,1]である.
すべての場合の数字が2次元配列に含まれる場合、[1,2,3],[1,3,2],[2,1,3],[2,3,1,3],[3,1,2],[3,2],[3,2,1,1]とすることができる.
返される値は3です.
注意事項
k内に重複する要素がないと仮定する.
I/O例
console.log(output);//3
console.log(output);//6
const factorial = (n) => {
if (n <= 1) return 1;
return n * factorial(n - 1);
};
1)パブリッシュ順序を含む変数を生成します.(初期値0)2)合計エントリ数がNの場合、どのエントリがすでに含まれているかを決定する配列が生成される.
3)0番目にスタックデータでfalseを生成し,それらをすべてfalseとして埋め込む.
let order = 0
const isUsed = new Array(N + 1).fill(false)
// N+1을 해주는 이유는 인덱스는 0부터 시작하지만 조는 1부터 시작하기 때문이다.
//K가 [2,3,1]라고 가정해보자 그리고 N이 3이다.
//isUsed === [false, false, false, false] 이다.
4)Kを問い合わせる場合,Kのiの第1グループを変数とする.5)ISUsedをチェックして使用済みかどうかを確認する(重複していないため)
6)numの前に現れる数字の配列をコピーし、
7)未使用数量を求める.
8)使用されていない数、それ以前のすべての状況をカウントします.
9)orderに追加します.
for(let i=0; i< K.length; i++) { //K=[2,3,1]
const num = K[i] //K[0] 은 2, 즉 num은 2
isUsed[num] = true //[false false true false]
const candidates = isUsed.slice(1, num) // [false]
const validCnt = candidates.filter((item) => item === false).length // 1개
const formerCnt = validCnt * factorial(N - i - 1);
order = order + formerCnt
}
最終的には、発表順序を含むorderを返します.リファレンス
https://lienkooky.tistory.com/77
Reference
この問題について([アルゴリズム]11109公開順序アルゴリズム#シーケンス#スタックデータ), 我々は、より多くの情報をここで見つけました https://velog.io/@jinlee122700/알고리즘-211109-발표순서-알고리즘-순열テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol