멘토링(완전탐색)

:raising_hand: 알고리즘 공부 간 기록이 필요한 문제들에 대한 정리를 기록하는 포스트 입니다.

1. 문제 요건

M 번의 테스트에 대한 등수값이 주어지고 그안에서 N 명의 멘토, 멘티가 가능한 경우의 수를 구하라 (단, 멘토는 모든 테스트에서 멘티보다 등수가 높아야함)

2. 코드

function solution(test) {
    let answer = 0
    let m = test.length // 테스트 횟수
    let n = test[0].length // 학생수
    let flag = 0
    // i 멘토 , j 멘티
    for(let i=1; i<= n; i++) {
        for(let j=1; j<= n; j++) {
            flag = 0 // 초기화
            for(let k=0; k< m; k++) {
                let pi = pj = 0 // 초기화
                for(let s=0; s< n; s++) {
                    // i, j 의 등수를 pi, pj 에 치환
                    if(test[k][s] === i) {
                        pi = s
                    } 
                    if(test[k][s] === j) {
                        pj = s
                    }
                }
                // 멘토 i 가 j 보다 등수가 높을경우
                if (pi < pj) {
                    flag++
                }
            }
            // 3번의 테스트 모두에서 멘티 j 보다 i가 등수가 높을 경우
            if(flag === m) {
                console.log(i,j)
                answer++
            }
            
        }
    }

    return answer
}

let test = [[3, 4, 1, 2], [4, 3, 2, 1], [3, 1, 4, 2]];

3. 결과정리

이번에 풀어본 문제는 블루투포스 완전탐색에 관련된 문제이다.

여기서 중요한점은 4번의 반복문을 통해 모든 경우의 수를 구하는 것이다.

먼저 i,j 를 시작값으로 한 반복문으로 4명의 인원이 각각 멘토, 멘티가 될 수 있는 경우의 수 16번을 모두 탐색한다는 의미이다.

그리고 그안에 k 반복문을 통해서 모든 테스트를 반복하고 s 를 통해 각 테스트에서 i,j 의 등수를 확인한다.

i,j 의 등수를 확인 후 i가 j 의 멘토가 될 수 있는 조건 즉, 등수가 3번의 테스트에서 모두 높다면 flag 값이 3이 되어있으며 이후 이러한 경우만 answer 값을 올려주어 멘토,멘티가 가능한 조건을 찾는다.

이방법은 사실 모두 검사해야하니 좋은방법은 아닌것 같지만 기록은 해두도록 한다.

4. Key Point

문제를 고민하고 또 고민하면서 풀어보고 강의를 통해 해답을 비교하며 찾게된 이번의 놓친 포인트는 첫번째 문제를 잘못 이해한 부분이 있었다.

문제가 복잡할 수록 조금 더 꼼꼼히 문제부터 제대로 이해한 뒤 알고리즘을 들어가야 할것이다.

두번째 놓친 포인트는 항상 그래왔지만 너무 복잡하게 생각하면 오히려 더 풀기가 힘들어 진다는 것이다.

이번에도 다시한번 위 풀이를 바탕으로 이해하고 다시한번 풀어보면서 유형을 익히도록 한다.

You may also enjoy