[Softeer] lv1. 나무심기 / Javascript

Softeer 나무심기 풀이 해설

1. 문제

남우는 나무를 2개 심으려고 합니다. 나무는 주어진 n개의 위치 중 서로 다른 두 곳에 꼭 심어야만 하며, 1번 위치부터 n번 위치까지 각 위치마다 토양의 비옥함에 해당하는 값 Fi가 주어졌을 때 남우는 나무가 심어지는 두 위치 a, b에서 토양의 비옥함의 곱인 Fa ∗ Fb가 최대가 되도록 나무를 심으려고 합니다. 남우가 적절한 위치에 나무를 심을 수 있도록 하는 프로그램을 작성해보세요.

 

만약 n이 3이고 다음과 같이 토양의 비옥함이 순서대로 5, -1, 4인 경우 5, 4 위치에 나무를 심으면 비옥함의 곱이 20으로 최대가 됩니다.

 

 

본 문제의 저작권은 (주)브랜치앤바운드에 있으며, 저작자의 동의 없이 무단 전재/복제/배포를 금지합니다.

제약조건

• 2 ≤ n ≤ 100
• -100 ≤ Fi ≤ 100

입력형식

첫 번째 줄에는 n이 주어집니다.
두 번째 줄에는 각 위치에서의 토양의 비옥함에 해당하는 정보 Fi가 각각 공백을 사이에 두고 주어집니다. Fi가 음수인 경우도 주어질 수 있음에 유의합니다.

출력형식

첫 번째 줄에 가능한 Fa ∗ Fb 값 중 최댓값을 출력합니다. 1 ≤ a, b ≤ n, a ≠ b 를 만족하는 경우 중 최대를 구해야 함에 유의합니다.

입력예제1

2 1 -1

출력예제1

-1

 

입력예제2

2 -1 -1

출력예제2

1

 

입력예제3

3 5 -1 4

출력예제3

20

 

입력예제4

3 -5 1 -4

출력예제4

20

 

2. 언어별 시간/메모리

나무심기 언어별 시간 메모리 요건

3. 풀이

const fs = require('fs');
const inputs = fs.readFileSync('/dev/stdin', 'utf8').trim().split('\n')

const n = Number(inputs[0]);
const arrF = inputs[1].split(' ').map(v => Number(v)).sort((a,b) => a-b);

if (n === 2) {
    console.log(arrF[0] * arrF[1])
} else {
    const normal = arrF[n-1] * arrF[n-2];

    if (arrF[0] < 0 && arrF[1] < 0) {
        const mValue = arrF[0] * arrF[1];
        console.log(Math.max(mValue, normal));
    } else {
        console.log(normal);
    }
}

핵심 아이디어

오름차순으로 sort 후, 제일 작은 숫자 2개의 곱과 제일 큰 숫자 2개의 곱을 비교하여 큰 것을 Pick

 

 

4. 시간복잡도

O(N log(N))

 

→ 따라서 최악의 경우에도 O(100 log(100)) = 대략 660번의 연산

 

5. 개선

정렬 없이 O(N)으로 풀 수 있는 방법이 있음.

순회하면서 가장 작은 수 2개와 가장 큰수 2개를 찾으면 됨

 

const fs = require('fs');
const inputs = fs.readFileSync('/dev/stdin', 'utf8').trim().split('\n')

const n = Number(inputs[0]);
const arr = inputs[1].split(' ').map(v => Number(v));

let firstMax = -Infinity
let secondMax = -Infinity
let firstMin = -Infinity
let secondMin = -Infinity

for (let num of arr) {
	if (num > firstMax) {
    	secondMax = firstMax;
    	firstMax = num;
    } else if (num > secondMax) {
    	secondMax = num
    }
    
	if (num < firstMin) {
    	secondMin = firstMin;
    	firstMin = num;
    } else if (num < secondMin) {
    	secondMax = num
    }
}

return Math.max(firstMax * secondMax, firstMin * secondMin);

 

구현에 만족하지말고 O(n)혹은 O(logN) 으로 구현할 수 있는 방법이 있는지 생각하자.