🔎 삼각 달팽이

❓ 문제링크

https://programmers.co.kr/learn/courses/30/lessons/12987

📄 제출 코드

function solution(A, B) {
    var answer = 0;
    let len = B.length;
    let left = 0;
    A.sort((a, b) => a-b);
    B.sort((a, b) => a-b);
    for (let i = 0; i < len; i++) {
        if (A[left] < B[i]) {
            answer += 1;
            left++;
         }
    }
    
    return answer;
}
let A = [5, 1, 3, 7];
let B = [2, 2, 6, 8];
console.log(solution(A, B));

이게 왜 level3? 이란 생각을 하면서 풀었지만, 효율성때문에 계속 안풀린 문제였다.
처음에는 일단 문제그대로 풀었다.

function solution(A, B) {
    var answer = 0;
    let len = B.length;
    for (let i = 0; i < len; i++) {
        let Amax = findMax(A);
        let Bmax = findMax(B);
        if (Bmax > Amax) {
            answer += 1;
            B.splice(B.indexOf(Bmax), 1);
        } A.splice(A.indexOf(Amax), 1);
        // console.log(`B: ${B}, A: ${A}`)
    }
    
    return answer;
}
function findMax(arr) {
    let max = 0;
    arr.forEach(el => {
        max <=el ? max = el : max=max
    })
    return max;
}
let A = [5, 1, 3, 7];
let B = [2, 2, 6, 8];
console.log(solution(A, B));

A와 B의 최대값을 찾아서 B가 A보다 더크면 answer+1하고, 해당위치의 값을 배열에서 삭제.
그러나 효율성에서 실패 당했다.

두 번째는 고민하다가 문득 굳이 순서가 상관없다는 생각이 들었다.
어차피 A에 맞춰서 B순서를 정하니까 A와 B를 정렬해서 비교해도 괜찮다고 생각했다.
그래서 방문체크를 할 visited배열을 추가하고, 방문체크를하면서 answer를 찾아나갔다.

function solution(A, B) {
    var answer = 0;
    let len = B.length;
    A.sort((a,b)=>a-b);
    B.sort((a,b)=>a-b);
    let visited = new Array(len).fill(false);
    for (let i = 0; i < len; i++) {
        for (let j = 0; j < len; j++) {
            if (A[i] < B[j] && !visited[j]) {
                visited[j] = true;
                answer += 1;
                break;
            }
        }
    }
    
    return answer;
}
let A = [5, 1, 3, 7];
let B = [2, 2, 6, 8];
console.log(solution(A, B));

하지만 이 역시도 효율성에서 탈락했다.
그렇게 마지막으로 나온 코드가 가장 위의 코드다.

function solution(A, B) {
    var answer = 0;
    let len = B.length;
    let left = 0;
    A.sort((a, b) => a-b);
    B.sort((a, b) => a-b);
    for (let i = 0; i < len; i++) {
        if (A[left] < B[i]) {
            answer += 1;
            left++;
         }
    }
    
    return answer;
}
let A = [5, 1, 3, 7];
let B = [2, 2, 6, 8];
console.log(solution(A, B));

A와 B를 정렬하고, A의 위치를 저장할 left. B를 돌면서 a<b면 left를 하나증가시켜 다음A를 비교.
이 때, 정렬을 했기 때문에 가장 낮은 거부터 큰 거를 찾아나간다.
주의! 정렬할 때 그냥 A.sort()하면 만약에 a가 [1,2,5,8,7,10]이러면 1,10,2,5,..로 정렬되니 조심.

📘 참고

https://angwangho.github.io/algorithm-숫자게임/