매일 LeetCode 풀기 | Two Sum / Time to Buy and Sell Stock

 

Two Sum

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.
 
Example 1:
Input: nums = [2,7,11,15], target = 9 Output: [0,1] Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
Example 2:
Input: nums = [3,2,4], target = 6 Output: [1,2]
Example 3:
Input: nums = [3,3], target = 6 Output: [0,1]
 
Constraints:
2 <= nums.length <= 104-109 <= nums[i] <= 109-109 <= target <= 109Only one valid answer exists.

 

class Solution {
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
        var dict = [Int:Int]()
        var answ: [Int] = []

        for (i,num) in nums.enumerated() {

            if let j = dict[target - num] {
                answ = [i,j]
            }

            dict[num] = i
        }
        return answ
    }
}

 

처음에는 반복문을 이용해서, 문제를 풀었다. 하지만 반복문은 시간복잡도가 O(n^2)이기 때문에, 해시 테이블을 이용한 접근 방식으로 새로 풀었다. 

 

접근 방식 (해시테이블)
1. [인덱스 : 숫자] 형식의 딕셔너리를 만든다.
2. 반복문을 돌면서 딕셔너리에 해당 인덱스와 숫자를 추가한다. 
2-1. 만약 추가하려는 숫자와 더했을 때 target이 되는 숫자가 이미 딕셔너리에 존재한다면 answ을 만들어 return 한다. 

 

 

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 <= 1050 <= prices[i] <= 104

 

class Solution {
    func maxProfit(_ prices: [Int]) -> Int {
        guard prices.count > 1 else { return 0 }
        
        var minPrice = prices[0]
        var maxProfit = 0 

        for price in prices[1...] {
            if price < minPrice {
                minPrice = price
            } else {
                maxProfit = max(maxProfit, price - minPrice)
            }
        }

        return maxProfit
    }
}

 

접근 방식 (단일 패스 알고리즘)
1. minPrice의 기본값을 배열의 0번째 원소로 한다. 
2. maxProfit의 기본값을 0으로 둔다. 
3. 1번째 원소부터 반복문을 돈다.
3-1. 만약 minPrice가 지금의 price값보다 크다면 minPrice를 지금의 price 값으로 업데이트 한다. 
3-2. 만약 minPrice가 지금의 Price보다 작다면 (= 지금의 Price가 minPrice보다 크다), 기존의 maxProfit과 (price - minprice) 를 비교해 maxProfit을 더 큰쪽으로 업데이트 한다. 
4. 전체 배열의 반복문을 다 돈 후에, maxProfit 값을 업데이트한다.