📌 문제
날마다 가격이 바뀌는 a의 가격을 모아 둔 정수 배열 prices가 주어집니다.
배열의 각 요소 prices[i]는 i일의 a의 가격을 나타냅니다.
매도는 무조건 매수 이후에 이루어져야 할 때, 한 번씩의 주식 매수와 매도를 통해 얻을 수 있는 최대 이익을 반환하세요.
만약 이익을 낼 수 없다면 0을 반환하세요.
prices의 길이는 2 이상 1000 이하이며, 가격은 0 초과 1000000 미만입니다.
✨ 해결 방법
초기 매수 가격을 배열의 첫 번째 요소로, 초기 최대 이익을 0으로 설정합니다.
배열의 각 요소를 돌면서 해당 요소에서 매도할 시 이익이 발생하는지 검사합니다.
예를 들어 정수 배열이 아래와 같다고 합니다.
prices = {100, 94, 95, 98, 96}
초기 매수 가격 = 100
최대 이익= 0
-
두 번째 요소(94)에서 매도
현재 시점 이익: 94 - 100 = -6
현재 최대 이익: max(0, -6) = 0
현재 최소 매수 가격: min(94, 100) = 94 -
세 번째 요소(95)에서 매도
현재 시점 이익: 95 - 94 = 1
현재 최대 이익: max(0, 1) = 1
현재 최소 매수 가격: min(94, 95) = 94 -
네 번째 요소(98)에서 매도
현재 시점 이익: 98 - 94 = 4
현재 최대 이익: max(0, 4) = 4
현재 최소 매수 가격: min(94, 98) = 94 -
다섯 번째 요소(96)에서 매도
현재 시점 이익: 96 - 94 = 2
현재 최대 이익: max(4, 2) = 4
현재 최소 매수 가격: min(94, 96) = 94
따라서 최종 최대 이익은 4 입니다.
이를 코드로 작성해봅시다.
💻 solution
function solution(A) {
if (A.length >= 2 && A.length <= 1000) {
// 초기 매수 가격을 배열의 첫 번째 요소로 설정
let minPrice = A[0];
// 초기 최대 이익을 0으로 설정
let maxProfit = 0;
// 배열의 두 번째 요소부터 마지막 요소까지 반복
for (let i = 1; i < A.length; i++) {
// 현재 매도 시점에서의 이익 계산
let currentProfit = A[i] - minPrice;
// 현재까지의 최대 이익과 현재 이익 중 큰 값을 선택
maxProfit = Math.max(maxProfit, currentProfit);
// 현재까지의 최소 매수 가격과 현재 주식 가격 중 작은 값을 선택
minPrice = Math.min(minPrice, A[i]);
}
return maxProfit;
}
}💻 solution develope
그런데 여기서 만약 매수값과 매도값을 함께 리턴해야 할 경우 코드를 보완해야 합니다. 현재 코드는 prices = {100, 96, 95, 98, 92} 처럼 배열 조합이 바뀔 경우 최소 매수 가격을 95가 아닌 92로 인식하기 때문입니다.
따라서 변수를 추가 설정하여 아래처럼 구성할 수 있습니다.
function solution(A) {
// 초기 매수 가격을 배열의 첫 번째 요소로 설정
let minPrice = A[0];
// 초기 최대 이익을 0으로 설정
let maxProfit = 0;
// 최대 이익이 발생한 시점의 매수 가격을 추적
let lastMinPrice = A[0];
// 최대 이익이 발생한 시점의 매도 가격을 추적
let sellPrice = A[1]; // 초기값으로 배열의 두 번째 요소 설정
// 배열의 두 번째 요소부터 마지막 요소까지 반복
for (let i = 1; i < A.length; i++) {
// 현재 매도 시점에서의 이익 계산
let currentProfit = A[i] - minPrice;
// 현재까지의 최대 이익과 현재 이익 중 큰 값을 선택
if (maxProfit < currentProfit) {
maxProfit = currentProfit;
// 이익이 발생한 시점의 매도 가격 업데이트
sellPrice = A[i];
}
// 현재까지의 최소 매수 가격과 현재 주식 가격 중 작은 값을 선택
minPrice = Math.min(minPrice, A[i]);
if (maxProfit === currentProfit) {
lastMinPrice = minPrice;
}
}
return {
maxProfit: maxProfit,
lastMinPrice: lastMinPrice,
sellPrice: sellPrice
};
}
const result = solution([100, 96, 95, 98, 92]);
console.log(result);💻 solution 2
function solution(A) {
let maxProfit = 0;
for (let i = 0; i < A.length - 1; i++) {
for (let j = i + 1; j < A.length; j++) {
const profit = A[j] - A[i];
if (profit > maxProfit) maxProfit = profit;
}
}
return maxProfit;
}위의 코드는 솔루션 1과 같은 답을 도출합니다. 하지만 모든 경우의 수를 순회하기 때문에 시간 복잡도가 O(N^2)이므로 배열의 크기가 커질수록 성능이 저하될 수 있습니다. 따라서 솔루션 1(그리디 알고리즘)을 사용하는 것을 지향합니다.
💔 solution
function solution(A) {
if (2 <= A.length && A.length <= 1000) {
let min = A[0];
let max = A[0];
// 최소값 (매수값)
for (let i = 1; i < A.length - 1; i++) {
if (0 < A[i] && A[i] <= 1000000) {
if (min > A[i]) {
min = A[i];
}
}
}
// 최소값이 인덱스 찾기
const minIndex = A.indexOf(min);
// 최대값 찾기
for (let i = minIndex + 1; i < A.length; i++) {
if (0 < A[i] && A[i] <= 1000000) {
if (max < A[i]) {
max = A[i];
}
}
}
const profit = max - min;
return profit;
}
}위의 코드를 작성하기 전 원래 작성했던 코드입니다.
해당 코드도 결과값에 알맞게 동작하지만, profit이 음수가 될 확률과 min값이 여러 개가 나타날 확률을 고려하지 못하고 있기 때문에 다른 값이 도출될 가능성이 있습니다.
