📌강의 정리
이 문제가 블루투포스 완전탐색을 쓰는 대표적인 문제이다.
하나하나의 경우를 전부다 확인해야한다.
앞을 멘토 뒤를 멘티로 한다.
총 경우의 수는 4*4로 16가지이다.
i가 멘토 j가 멘티라고 가정하고 문제를 푼다.
각각의 테스트마다 하나하나 다 비교해야한다.
또한 포문 두개가 더 돈다 총 4중 포문이다.
forfor ij 로 16번 다 돌면서 forfor sk로 하나씩 멘토멘티의 경우를 다 비교해본다.
그렇게 비교하며 예를들어 (3,1)이 맞는 멘토멘티인지 확인하려면
test[k][s] === i test[k][s] === j
를 하며 하나의 멘토 멘티 짝이 모든시험에서 다 통과하는지를 확인한다.
입력 배열을 test로 받고 m테스트갯수를 test.length로 3을 구한다.
학생수n은 test[0].length로 4를 구해 문제의 조건들을 구한다.
이중포문으로 i j가 n번 돌게 하여 i,j 의 16가지를 다 구한다.
그 안에서 다시 포문을 0번부터 m개를 구하고 다시 그 안에서 n번돈다.
이후 test[k][s] === i 로 pi와 pj를 구한다.
이제 이 pi와 pj를 비교하여 pj가 크면 cnt++하여 m과 비교해 같으면 앤서를++한다.
📌느낀점
역대급으로 어려운 문제였다.
처음엔 문제도 해석하기에 따라 문제가 달라져서 잘못이해했었지만
결국에는 풀어냈다.
이 문제를 풀어냄으로써 블루투포스에 아주 조금이나마 성취도를 쌓은 것 같다.
나는 처음부터 등수가 높은 것만 뽑아내 i가 0일때에서 일치하는것만 다시 다른 배열에
집어넣어 그 배열의 길이를 구하는 식으로 했는데 이렇게 하면 풀리긴하지만
포문을 6개써야하고 블루투포스에도 거리가 좀 있으며 복잡하다.
강사님의 방법을 사용하면 블루투포스에도 잘 부합하고 가독성도 좋다.
이 문제를 잘 이해하고 암기하며 내것으로 만들어야겠다.
//220609 추가
<html>
<head>
<meta charset="UTF-8" />
<title>출력결과</title>
</head>
<body>
<script>
function solution(test) {
let answer = 0;
let n = test[0].length;
let m = test.length;
let formArr = [];
let answerArr = [];
//for문을 돌려 첫번째 배열의 부분집합같은 배열을 만듭니다.
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
for (let k = j + 1; k < n; k++) {
if (i === 0) {
console.log("처음에 formArr에 집어넣는 배열", [
test[i][j],
test[i][k],
]);
formArr.push([test[i][j], test[i][k]]);
console.log("formArr = ", formArr);
} else {
//두번째 for문에서 만들어진 부분집합들을 원본과 비교해
for (let l = 0; l < formArr.length; l++) {
if (
JSON.stringify(formArr[l]) ==
JSON.stringify([test[i][j], test[i][k]])
)
//있으면 새로운 배열에 넣어주고
answerArr.push([test[i][j], test[i][k]]);
}
}
}
}
//마지막반복에 이 새로운배열을 첫번째 배열에 넣어줍니다.
if (i !== 0) formArr = answerArr;
//새로운 배열 초기화
answerArr = [];
}
//계속 반복하고 마지막에 이 첫번째 배열의 길이를 출력합니다.
console.log("정답배열은 = ", formArr);
answer = formArr.length;
return answer;
}
let arr = [
[3, 4, 1, 2],
[4, 3, 2, 1],
[3, 1, 4, 2],
];
console.log(solution(arr));
</script>
</body>
</html>//나의코드
<html>
<head>
<meta charset="UTF-8">
<title>출력결과</title>
</head>
<body>
<script>
function solution(test){
let answer=0;
let arrRes = [];
let arrTest = [];
let arrTest2 = [];
for(let i=0;i<test.length;i++){
if(i === 0){
for(let j=0;j<test[i].length;j++){
for(let k=j+1;k<test[i].length;k++){
arrTest.push(test[i][j]);
arrTest.push(test[i][k]);
arrRes.push(arrTest);
arrTest = [];
}
}
}
else{
console.log(arrRes)
for(let j=0;j<test[i].length;j++){
for(let k=j+1;k<test[i].length;k++){
arrTest.push(test[i][j]);
arrTest.push(test[i][k]);
for(let l=0; l<arrRes.length; l++){
if(arrRes[l][0] === arrTest[0]){
if(arrRes[l][1] === arrTest[1]){
arrTest2.push(arrTest);
}
}
}
arrTest = [];
}
}
arrRes = arrTest2;
arrTest2 = [];
}
console.log(arrRes)
}
answer = arrRes.length
return answer;
}
let arr=[[3, 4, 1, 2], [4, 3, 2, 1], [3, 1, 4, 2]];
console.log(solution(arr));
</script>
</body>
</html>
//강사님 코드
<html>
<head>
<meta charset="UTF-8">
<title>출력결과</title>
</head>
<body>
<script>
function solution(test){
let answer=0;
m=test.length;
n=test[0].length;
for(let i=1; i<=n; i++){
for(let j=1; j<=n; j++){
let cnt=0;
for(let k=0; k<m; k++){
let pi=pj=0;
for(let s=0; s<n; s++){
if(test[k][s]===i) pi=s;
if(test[k][s]===j) pj=s;
}
if(pi<pj) cnt++;
}
if(cnt===m) answer++;
}
}
return answer;
}
let arr=[[3, 4, 1, 2], [4, 3, 2, 1], [3, 1, 4, 2]];
console.log(solution(arr));
</script>
</body>
</html>
'JS 알고리즘 문제풀이 > 섹션 4. 완전탐색(블루투포스)' 카테고리의 다른 글
| 5.K번째 큰 수 (0) | 2022.01.14 |
|---|---|
| 4.졸업선물 (0) | 2022.01.14 |
| 2.뒤집은 소수 (0) | 2022.01.14 |
| 1.자리수의 합 (0) | 2022.01.14 |