개발일지/TIL

[leetcode] 121. Best Time to Buy and Sell Stock(못 푼 문제)

JangKroed 2023. 8. 24. 23:03
728x90
반응형

Best Time to Buy and Sell Stock

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

 

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Example 2:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.

 

Constraints:

  • 1 <= prices.length <= 105
  • 0 <= prices[i] <= 104

 

풀이 - 1

function maxProfit(prices: number[]): number {
  const minIndex = prices.findIndex((e) => e === Math.min(...prices));

  const arr = prices.slice(minIndex, prices.length - 1);
  const maxIndex = arr.findIndex((e) => e === Math.max(...arr));

  const result = arr[maxIndex] - prices[minIndex];

  return result > 0 ? result : 0;
}

최소값 이후의 요소부터 끝까지 slice한 배열에서 최대값을 구하면 간단하게 풀수있을거라 생각했지만 문제를 제대로 이해하지 못해 마지막 요소에 최소값이 있고 이전요소에서 충분히 이익을 낼 수 있음에도 0을 리턴하였다.

prices = [2,4,1]의 케이스에서 실패했다.

 

풀이 - 2

정말 피하고 싶었지만, 중첩반복문을 활용하여 객체에 배열의 요소마다 최대값을 저장하는 방식을 사용해보면 일단은 구현이 가능하지 않을까 싶었다.

function maxProfit(prices: number[]): number {
  const obj: { [key: number]: number } = {};

  for (let i = 0; i < prices.length; i++) {
    obj[prices[i]] = 0;
    for (let y = i + 1; y < prices.length; y++) {
      if (obj[prices[i]] < prices[y]) {
        obj[prices[i]] = prices[y];
      }
    }
  }

  let min: number, max: number;

  for (const key in obj) {
    const start: number = Number(key);
    const end: number = obj[key];

    if (start > end) {
      continue;
    }

    if (!min! && !max!) {
      min = start;
      max = end;
    }

    if (min! > start && max! <= end) {
      min = start;
      max = end;
    }
  }

  let result: number = max! - min!;
  if (!result) {
    result = 0;
  }

  return result;
}

사실 정확하게 이해는 되지 않지만 prices = [3,2,6,5,0,3]의 케이스에서 실패하였다.

수정사항으로는 좀더 단순화하고 사용하지 않아도 될 변수 제거하는 정도가 있을것 같았다.

 

풀이 - 3

단순화랑 변수제거도 좋지만 좀더 근본적인 문제가 생겼다

function maxProfit(prices: number[]): number {
  const obj: { [key: number]: number } = {};

  for (let i = 0; i < prices.length; i++) {
    obj[prices[i]] = 0;
    for (let y = i + 1; y < prices.length; y++) {
      if (obj[prices[i]] < prices[y]) {
        obj[prices[i]] = prices[y];
      }
    }
  }

  let result: number = 0;

  for (const key in obj) {
    const min: number = Number(key);
    const max: number = obj[key];

    if (min > max) {
      continue;
    }

    if (result <= 0) {
      result = max - min;
    }

    if (result < max - min) {
      result = max - min;
    }
  }

  if (result <= 0) {
    result = 0;
  }

  return result;
}

prices = [1,4,1,4,3,1]의 케이스처럼 중복되는 요소가 있을시 객체를 사용하다보니 덮어씌워져서 차라리 배열을 사용하는 편이 나을것 같았다.

 

풀이 - 4

function maxProfit(prices: number[]): number {
  const arr: string[] = [];

  let result: number = 0;

  for (let i = 0; i < prices.length; i++) {
    for (let y = i + 1; y < prices.length; y++) {
      if (!arr[i]) {
        arr.push(`${prices[i]} ${prices[y]}`);
      }

      const [min, max] = arr[i].split(" ");

      if (Number(max) < prices[y]) {
        arr[i] = `${min} ${prices[y]}`;
      }

      if (prices[y] - prices[i] > result) {
        result = prices[y] - prices[i];
      }
    }
  }

  return result;
}

확실히 풀이가 될지는 몰라도 중첩반복문에 split를 사용하게되어 시간복잡도상 좋지않을거같다는 생각은 들었는데 혹시나가 역시나라고 하였는가.. Time Limit Exeeded가 나오고야 말았다..

일단 더이상 해결방법이 보이지않아 처음으로 킵해두었다가 나중에 풀어볼 문제로 남겨봐야겠다..

728x90
반응형