ランキング
14144 ワード
序文
最近Jestと勉強していた時は時間が足りなくて1日に1題も解けなかったので見逃してしまいましたううう
時間をうまく管理できなかった言い訳ですが、見逃してしまったので、週末はなるべく協力しましょう.
この問題は最初はどのようにグラフで解決しようかと考えていましたが、考えてみるとアプローチ方法を思いつき、それをもとに実施しました.その後、時間がかかったので、他の人がどのようにこの問題に近づいたのか知りたいです.
ソースコード
隣接行列を構築して解決した.まず隣接行列を作り,各要素で勝つと「W」,負けると「L」を代入する.
そして、隣接行列に基づいて、図形をBFSにナビゲートする.しかし勝ちのみを確認する探索と負けのみを確認する探索の2段階に分けて行い,以下の変数を宣言した.
各ノードの隣接行列をBFSにより探索し,いくつかの勝ち点ノードといくつかの負け点を計算した.勝ったらwincnt 1を増やし、負けたらlosetcnt 1を増やします.
そして.
wincnt+losecntの和がn-1に等しいことは,自分以外のすべてのノードと比較したことを意味するので,自分の正しい順序を知る.正解1が追加されました.
これにより、すべてのノードが検索され、最終的な答えが答えに含まれ、返されると正しい答えになります.
ポスト
人の解答を見ていないで、ただ自分の考えによって解答して、だから想像の中で少し時間を使いました.でも嬉しいし、今はある程度BFSに慣れているので自信もあります.
他の人がどのようにこの問題に近づいているのか、他のアルゴリズムで解決できるかどうかを見てみましょう.他人のコードを見るのも大きな勉強だからです.
最近Jestと勉強していた時は時間が足りなくて1日に1題も解けなかったので見逃してしまいましたううう
時間をうまく管理できなかった言い訳ですが、見逃してしまったので、週末はなるべく協力しましょう.
この問題は最初はどのようにグラフで解決しようかと考えていましたが、考えてみるとアプローチ方法を思いつき、それをもとに実施しました.その後、時間がかかったので、他の人がどのようにこの問題に近づいたのか知りたいです.
ソースコード
/*
제한 사항
- 선수의 수는 1명 이상 100명 이하입니다.
- 경기 결과는 1개 이상 4,500개 이하입니다.
- results 배열 각 행 [A, B]는 A 선수가 B 선수를 이겼다는 의미입니다.
- 모든 경기 결과에는 모순이 없습니다.
*/
function solution(n, results) {
let answer = 0;
const adjArray = new Array(n + 1);
for (let i = 1; i <= n; i++) {
adjArray[i] = new Array(n + 1).fill('');
}
results.forEach(result => {
adjArray[result[0]][result[1]] = 'W';
adjArray[result[1]][result[0]] = 'L';
});
Loop: for (let i = 1; i <= n; i++) {
const winQ = [i];
const loseQ = [i];
const winV = [];
const loseV = [];
let winCnt = 0;
let loseCnt = 0;
while (winQ.length !== 0) {
if (winCnt + loseCnt === n - 1) {
answer++;
continue Loop;
}
const current = winQ.shift();
for (let j = 1; j <= n; j++) {
if (adjArray[current][j] === 'W' && !winV.includes(j)) {
winCnt++;
winQ.push(j);
winV.push(j);
}
}
}
while (loseQ.length !== 0) {
if (winCnt + loseCnt === n - 1) {
answer++;
continue Loop;
}
const current = loseQ.shift();
for (let j = 1; j <= n; j++) {
if (adjArray[current][j] === 'L' && !loseV.includes(j)) {
loseCnt++;
loseQ.push(j);
loseV.push(j);
}
}
}
}
return answer;
}
問題を解く隣接行列を構築して解決した.まず隣接行列を作り,各要素で勝つと「W」,負けると「L」を代入する.
そして、隣接行列に基づいて、図形をBFSにナビゲートする.しかし勝ちのみを確認する探索と負けのみを確認する探索の2段階に分けて行い,以下の変数を宣言した.
const winQ = [i];
const loseQ = [i];
const winV = [];
const loseV = [];
let winCnt = 0;
let loseCnt = 0;
winqとloseqはそれぞれBFSを迂回するためのキューである.また,winVとloseVは各キューのアクセスノードを決定するための配列であり,wincntとlosecntはそれぞれ勝ち点数と真点数を計算するための変数である.各ノードの隣接行列をBFSにより探索し,いくつかの勝ち点ノードといくつかの負け点を計算した.勝ったらwincnt 1を増やし、負けたらlosetcnt 1を増やします.
そして.
if (winCnt + loseCnt === n - 1) {
answer++;
continue Loop;
}
以上のように,勝った数とアレイ数がn−1に等しいと,これ以上確認する必要がないので,正解を増やして次のノードを探索する.wincnt+losecntの和がn-1に等しいことは,自分以外のすべてのノードと比較したことを意味するので,自分の正しい順序を知る.正解1が追加されました.
これにより、すべてのノードが検索され、最終的な答えが答えに含まれ、返されると正しい答えになります.
ポスト
人の解答を見ていないで、ただ自分の考えによって解答して、だから想像の中で少し時間を使いました.でも嬉しいし、今はある程度BFSに慣れているので自信もあります.
他の人がどのようにこの問題に近づいているのか、他のアルゴリズムで解決できるかどうかを見てみましょう.他人のコードを見るのも大きな勉強だからです.
Reference
この問題について(ランキング), 我々は、より多くの情報をここで見つけました https://velog.io/@munyohan/순위-문제-풀이テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol