24-05-21 알고리즘 문제 풀이

오늘도 Spring을 계속 학습하면서 시간을 보냈다. 여전히 알아야 할 것이 너무나도 많다. 이전에 무심코 썼었던 기능들이 어떤 방식으로 작동하는지, 왜 이것을 사용해야하는지를 이해하려다보니 시간이 더 오래 소모되는 것 같다. 이미 과제의 필수로 구현해야하는 부분을 구현하는 법은 익혔기 때문에 이제는 제대로 공부를 해서 이해하고 넘어가는게 중요하다고 생각한다.

 

여기에는 오늘 풀어보았던 알고리즘 문제 풀이 과정 하나를 적어보았다.

1. 알고리즘 문제 풀이

1-1. 풀어본 문제

leetcode에 있는 '121. Best Time to Buy and Sell Stock' 문제를 풀어보았다.

 

[문제]

prices[i]가 i번째 날의 주식 가격인 배열 prices가 주어집니다.

 

당신은 주식을 구매할 날짜를 하나 선택하고, 미래에 주식을 팔 다른 날짜 하나를 선택해서 수익을 극대화 하고 싶습니다.

 

거래에서 당신이 얻을 수 있는 최대 수익을 반환해주세요. 만약 수익을 달성할 수 없다면 0을 반환하세요.

 

- 예시 1

입력: prices = [7,1,5,3,6,4]

출력: 5

설명: 2번째 날(가격: 1)에 구입한 다음 5번째 날(가격: 6)에 판매하게 되면 6-1 = 5의 수익을 얻게 된다.

판매하기 전에 구매를 먼저 해야하기 때문에 2번째 날에 구매한 다음 첫 번째 날에 판매하는 것은 허용되지 않으니 유의하세요.

 

 

- 예시 2

입력: prices = [7,6,4,3,1]

출력: 0

설명: 이 경우에는, 거래가 이루어지지 않고 수익이 0이 됩니다.

 

제한 사항:

• 1 <= prices.length <= 100000
• 0 <= prices[i] <= 1000

 

1-2. 문제 풀이

문제를 어떻게 풀까 곰곰히 생각해 보았는데 결국 첫째날부터 마지막 날 까지 한 번만 전체 조회를 하면 문제를 풀 수 있다는 것을 알게 되었다. 사야지 팔 수 있기 때문에 첫째날부터 하나하나 조회해 가면서 여태까지 날들 중 최저가격과 여태까지 얻을 수 있는 최대수익을 구해주기만 하면 쉽게 풀 수 있다.

 

먼저 최대 수익은 0으로 두고 시작하고, 최저가격은 첫째날의 가격으로 시작한 뒤 하나하나 조회해줄때마다 업데이트를 해주는 식으로 코드를 작성하면 된다.

 

코드가 짧고 간단하기 때문에 주석과 함께 보면 이해가 어렵지 않을 것이다.

class Solution {
    fun maxProfit(prices: IntArray): Int {
        // 최대수익은 0, 최저가격은 첫째 날의 가격으로 먼저 시작하게 된다.
        var maxProfit = 0
        var minPrice = prices[0]

        for (price in prices) {
            // 최대 수익은 현재 조회 가격에서 최저가격을 뺀 값이
            // 이전의 최대 수익보다 크다면 값이 바뀌게 된다.
            // coerceAtLeast와 coerceAtMost를 사용했는데
            // 이는 Math 패키지의 min(), max()를 사용한 것과 같다.
            // maxProfit = max(price-minPrice,maxProfit)
            maxProfit = (price-minPrice).coerceAtLeast(maxProfit)
            
            
            // 최저 가격도 현재 조회 가격과 비교해 업데이트 된다.
            minPrice = minPrice.coerceAtMost(price)
            // minPrice = min(minPrice,price)
        }

    return maxProfit

    }
}

이 문제에서도 새로 알게된 coerceAtLeast와 coerceAtMost를 사용해보았다. Math 패키지를 import 해야해서 불편함이 있지만 min과 max를 사용하는게 좀 더 직관적이고 위 함수를 모르는 사람이 볼때는 더 잘 이해될 수도 있겠다라는 생각이 들었다. 어떤 것이 더 나은 것인지는 더 고민을 해보아야겠다.

 

2. 오늘 배운 것

- 오늘은 JPA의 작동방식에 대해서 어느정도 파악한 것 같다. 이것에 대해서도 정리를 해보고 싶긴 한데 이해하고 정리하려니 쉽지가 않은 것 같다.

- Spring의 전체적인 작동 방식을 파악하는 것에 주력하고 있다. 완전히 이해한 다음에는 다시 과제로 돌아가 코드를 작성할 예정이다. 예상보다 시간이 좀 걸리긴했는데, 완전히 이해하고 넘어가는 것이 더 중요할 것 같다.