[알고리즘] 코딩테스트 연습 - [JavaScript] 최솟값 만들기

https://school.programmers.co.kr/learn/courses/30/lessons/12941

프로그래머스

본 포스팅에서 다루는 문제는 위 프로그래머스 링크를 통하여 문제 확인 및 풀이가 가능합니다!

 

 

1. 문제 풀이

 문제 설명 자체는 쉬운 문제입니다. 길이가 같은 두 배열이 주어지고 배열에서 각각 하나의 원소를 뽑아 곱한 뒤 더한 값이 최소가 되도록 하는 것이 목표이며 이 최솟값을 반환하는 것이 문제의 전부입니다.

 

 곱 연산의 성질을 제대로 이해하고 있다면 각 원소에서 뽑아야 하는 값은 쉽게 알 수 있습니다. 우리는 배열 A, B가 있을 때 A에서 가장 큰 원소와 B에서 가장 큰 원소를 곱한 뒤 더하고, 그 다음으로 가장 큰 A의 원소와 B의 원소를 곱한 뒤 더하는 것을 배열 길이만큼 반복하면 답을 구할 수 있습니다.

 

 따라서 배열 A, B 중 하나는 오름차순, 나머지 하나는 내림차순으로 정렬한 뒤, 순차적으로 원소에 접근하여 곱한 값을 모두 더해주기만 하면 되는 문제입니다.

 

2. 실패 코드(시간초과, 69.6점)

function solution(A,B){
    var answer = 0;
    // 배열 A와 B 모두 오름차순으로 정렬
    A.sort((a, b) => a - b);
    B.sort((a, b) => a - b);
    
    let len = A.length;
    
    for (let i = 0; i < len; i++) {
    	// A는 앞에서부터 B는 뒤에서부터 접근하여 각 원소의 곱을 answer에 더해줌
        answer += A[i] * B[len-1-i];
    }
    return answer;
}

 

 위 코드는 배열 A, B를 모두 오름차순으로 정렬시키고 배열 A는 앞에서부터 B는 뒤에서부터 접근하도록 하였습니다.

 

 이 경우, 정확성 테스트는 모두 통과하였으나 효율성 테스트는 모두 실패하였습니다. 

 

3. 정답 코드

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

    return answer;
}

 

 정답 코드와 위 실패 코드는 크게 다르지 않습니다. 차이점으로는 A는 오름차순, B는 내림차순으로 정렬시킨 뒤, 배열 A와 B 모두 index인 i 를 통하여 접근하는 것을 볼 수 있습니다.

 

 위 실패코드에서는 배열 B의 원소에 접근할 때 len - 1 - i 을 통하여 접근하기 때문에 변수 len, i에 접근하는 시간과 감소 연산 시간이 추가로 들게 되는 것입니다.

 

4. 마치며

 

 위 정답코드에서도 설명드린 것처럼 자주 접근하는 값은 변수에 할당하여 해당 값을 재사용하는 것이 좋습니다(위 사진에서는 A.length를 for문의 반복 조건 체크마다 사용하기 때문에 len이라는 변수에 할당).

 

 또한, 두 개의 배열을 서로 반대로 접근해야 하는 경우에는 한 배열은 오름차순, 나머지 배열은 내림차순 한 뒤 i라는 하나의 변수를 통하여 접근하는 것이 코드의 효율성을 높일 수 있습니다.

 

 문제를 풀면서 놓치고 있던 부분인 '불필요한 연산 및 반복 작업을 줄이는 것'이 효율적인 코드를 만드는 것임을 다시금 깨닫게 해주는 문제였습니다.