반례가 있는지 알 수 있을까요?

function solution(arr) {

    let result = [];

    const convertArray = arr;

    for (let i = 0; i < arr[0].length - 1; i++) {

        const mento = arr[0][i];

        for (let j = 0; j < arr.length; j++) {

            for (let k = 0; k < arr.length; k++) {

                const menti = arr[k][j];

                if (j > i) {
                    break;
                };

                if (j !== k) {
                    if (mento <= menti) {

                        const index = convertArray[k].indexOf(menti);

                        convertArray[k][index] = 'not';
                    }
                };    
                 
            };

        };

    };

    for (let i = 0; i < arr[0].length - 1; i++) {
        const mento = arr[i][i];

        for (let k = 0; k < arr[0].length; k++) {

            const menti = convertArray[i][k];
    
            if (typeof menti === 'number' && mento !== menti && typeof mento === 'number') {
    
                result.push([mento, menti]);
            };
    
        };
        
    }
    return result.length;
};

저는 위처럼 풀었습니다.

제가푼건 O(n^3) + O(n^2)인 것 같은데
제가 푼 방법에서 반례가 있을까요?
다른 케이스들로 시뮬레이션 돌렸는데 잘 생각이 나지 않아 질문드립니다.

안녕하세요, 인프런 AI 인턴입니다.

제시해 주신 코드를 살펴보니, 멘토-멘티를 찾는 로직으로 해석됩니다.
코드의 의도가 각 테스트 케이스에서 학생들의 등수를 비교하여 멘토-멘티 관계를 도출하는 것으로 보이는데, 아래와 같은 부분에서 문제가 발생할 수 있습니다.

if (j > i) break; 부분에서 멘티가 멘토보다 등수가 앞선 경우에만 비교를 중단하는 로직은 멘티가 멘토보다 항상 뒤에 있어야 하는 것을 가정한 것 같습니다. 하지만 이는 주어진 문제의 조건에 따라 반드시 성립하지 않으므로 이러한 경우 반례가 발생할 수 있습니다.
convertArray를 사용하여 일부 값을 ‘not’으로 변경하고 있지만, 이 변경이 결과 산출 로직에 어떻게 영향을 미치는지 명확하지 않습니다. convertArray의 값이 ‘not’으로 변경된 후에 어떤 로직에 의해 이를 활용하는지 이해하기 어렵습니다. 이에 따라 결과 로직으로 올바른 멘토-멘티 쌍의 개수를 산출하는 데 문제가 있을 수도 있습니다.
result 배열에 멘토-멘티 쌍을 담는 과정에서, 실제로 멘토-멘티 관계가 성립하는지 여부를 검증하는 단계가 부족해 보입니다. 모든 경우를 올바르게 처리하고 있는지 확인이 필요합니다.

반례를 찾기 위해서는 다음과 같은 경우들을 살펴보시면 좋을 것 같습니다:
- 멘티가 한 상황에서는 멘토보다 상위 등수를, 다른 상황에서는 멘토보다 하위 등수를 가진 경우
- 멘토-멘티 관계가 되지 않아야 하는 쌍이 result 배열에 포함되어 있는지 검사

보다 구체적인 반례를 찾기 위해서는 여러 다양한 테스트 케이스를 손으로 그려보거나 작은 입력 값을 이용하여 직접 시뮬레이션 해보는 것이 좋습니다.

질문에 도움이 되셨길 바랍니다. 추가로 질문이 있다면 언제든지 문의해 주세요!

인프런 커뮤니티 질문&답변