들어가며
이 포스팅에서는 leetcode 추천 문제 top 75를 자바스크립트로 풀어보며 자바스크립트 공부와 알고리즘 공부를 동시에 합니다. 문제와 풀이를 적을 건데, 틀린 부분이나 더욱 개선될 부분이 있다면 댓글로 달아주시면 정말 감사하겠습니다.
문제
Best Time to Buy and Sell Stock
문제 설명
문제 개요
이 문제의 입력은 prices로 각 시점의 주가가 들어온다. 그리고 우리가 구해야 하는 것은 이 각 시점의 주가에서 최대의 이익을 계산해야 합니다.
예제
입력 : [7,1,5,3,6,4]
출력 : 5
여기서 출력이 5인 이유는, 주가가 1일때 사서 6일 때 팔면 최대의 이익이 남기 때문입니다.
풀이 과정
두 가지 풀이를 생각해내었습니다.
첫번째 풀이는 '차를 전부 확인해보면 된다'라는 접근법에서 나왔습니다. 현 시점에서 내 뒤에 있는 값들의 차를 전부 계산해서 그 차가 가장 큰 (이득이 가장 큰) 값을 찾는 것입니다.
소스는 다음과 같이 나왔습니다.
/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function(prices) {
let max = 0;
for(let i=0; i<prices.length; i++){
for(let j=i+1; j<prices.length; j++){
let diff = - (prices[i] - prices[j]);
max = max < diff ? diff : max
}
}
return max;
};이 경우 복잡도는 n제곱이 나옵니다.
두번째 풀이는 '앞서 나왔던 가장 최소값을 기억하고 그 값을 이용해 차를 계산하고, 만일, 최소 값보다 작은 값이 나온다면 최소 값을 업데이트 한다.'라는 접근법에서 나왔습니다.
/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function(prices) {
let min = prices[0];
let max_diff = 0;
for(let i=1; i<prices.length; i++){
if(prices[i] < min){ // set start point
min = prices[i];
}
else {
let diff = prices[i] - min;
if(diff > max_diff){
max_diff = diff;
}
}
}
return max_diff;
};위 방법이 거의 베스트 케이스로 나왔습니다. O(n)만큼만 반복하면 정답이 나오게 됩니다.
배운 점
하나의 배열에서 배열의 두 수의 관계에 대한 값을 추출하려 이중 루프를 돌 때는 역시 신중해야 하는 것 같습니다.
위의 경우에는 주식의 시점이라는 특성 때문에 최대의 이익을 구할 때, 자신보다 먼저 일어난 숫자들 (현 시점에서 내 앞에 있는 인덱스들)의 값은 중요하지 않다는 점에 초점을 맞추어
전부 루프를 돌며 값을 계산해보기보다는 최대 이익을 구할 수 있는지 확인하며, 값을 업데이트하는 방식으로 O(n)의 시간복잡도로 풀어낼 수 있었습니다.
