๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

์ฝ”๋”ฉํ…Œ์ŠคํŠธ/ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค

[Javascript] ์ตœ์†Ÿ๊ฐ’ ๋งŒ๋“ค๊ธฐ (12941)

๋ฌธ์ œ๋งํฌ

 

์ฝ”๋”ฉํ…Œ์ŠคํŠธ ์—ฐ์Šต - ์ตœ์†Ÿ๊ฐ’ ๋งŒ๋“ค๊ธฐ

๊ธธ์ด๊ฐ€ ๊ฐ™์€ ๋ฐฐ์—ด A, B ๋‘๊ฐœ๊ฐ€ ์žˆ์Šต๋‹ˆ๋‹ค. ๊ฐ ๋ฐฐ์—ด์€ ์ž์—ฐ์ˆ˜๋กœ ์ด๋ฃจ์–ด์ ธ ์žˆ์Šต๋‹ˆ๋‹ค. ๋ฐฐ์—ด A, B์—์„œ ๊ฐ๊ฐ ํ•œ ๊ฐœ์˜ ์ˆซ์ž๋ฅผ ๋ฝ‘์•„ ๋‘ ์ˆ˜๋ฅผ ๊ณฑํ•ฉ๋‹ˆ๋‹ค. ์ด๋Ÿฌํ•œ ๊ณผ์ •์„ ๋ฐฐ์—ด์˜ ๊ธธ์ด๋งŒํผ ๋ฐ˜๋ณตํ•˜๋ฉฐ, ๋‘ ์ˆ˜๋ฅผ ๊ณฑ

programmers.co.kr

 

์ ‘๊ทผ ๋ฐฉ๋ฒ•

๋‘ ๋ฐฐ์—ด(A,B)์˜ ๊ณฑ์˜ ํ•ฉ์ด ์ตœ์†Œ๊ฐ€ ๋ ๋ ค๋ฉด A์˜ ์ตœ์†Ÿ๊ฐ’๊ณผ B์˜ ์ตœ๋Œ€๊ฐ’์„ ๊ณ„์†ํ•ด์„œ ๊ณฑํ•˜๋ฉด ๋œ๋‹ค.

์ฒ˜์Œ์—” ๊ทธ๋ƒฅ ๋งˆ์Œ์ด ๊ฐ€๋Š”๋Œ€๋กœ ํ’€์–ด๋ณด์•˜๋‹ค.

1. A๋ฐฐ์—ด์˜ ์ตœ๋Œ€๊ฐ’๊ณผ B๋ฐฐ์—ด์˜ ์ตœ์†Ÿ๊ฐ’์„ ๊ณฑํ•˜์—ฌ answer์— ๋‹ด๊ณ 

2. A๋ฐฐ์—ด๊ณผ B๋ฐฐ์—ด์—์„œ ์‚ฌ์šฉํ•œ ์ตœ๋Œ€๊ฐ’๊ณ  ์ตœ์†Ÿ๊ฐ’์„ ์ œ๊ฑฐํ•จ


ํ•˜์ง€๋งŒ ๋ฐฐ์—ด์˜ ์ค‘๊ฐ„๊ฐ’ ์ œ๊ฑฐ๋Š” ๊ณ„์†ํ•ด์„œ index๋ฅผ ์ƒˆ๋กœ ํ• ๋‹นํ•ด์•ผํ•˜๊ธฐ ๋•Œ๋ฌธ์— O(N)์œผ๋กœ ๋น„ํšจ์œจ์ ์ด๋‹ค.


๋‹ค์‹œ ์ข‹์€ ๋ฐฉ๋ฒ•์„ ๋– ์˜ฌ๋ ค A๋Š” ์˜ค๋ฆ„์ฐจ์ˆœ์œผ๋กœ B๋Š” ๋‚ด๋ฆผ์ฐจ์ˆœ์œผ๋กœ ์ •๋ ฌํ•˜๊ณ  ๊ณฑํ•˜๋Š” ๋ฐฉ์‹์œผ๋กœ ํ’€์—ˆ๋‹ค.

 

// ํšจ์œจ ์ข‹์€ ํ’€์ด

function solution(A,B){
    var answer = 0;
    A.sort((a,b) => a - b);
    B.sort((a,b) => b - a);
    
    for(let i = 0; i < A.length; i++){
        answer += A[i] * B[i]
    }

    return answer;
}
// ํšจ์œจ ๋‚˜์œ ํ’€์ด

function solution(A,B){
    var answer = 0;

    while(A.length > 0){
        let aMin = Math.min(...A);
        let bMax = Math.max(...B);
        let aMinIdx = A.indexOf(aMin);
        let bMaxIdx = B.indexOf(bMax);
        answer += aMin * bMax;
        
        A.splice(aMinIdx, 1);
        B.splice(bMaxIdx, 1);
    }

    return answer;
}