[백준] (Swift) 11501번 - 주식 (실버2, 그리디)

실버2여서 쉬운 문제였지만, 왜 실버2야? 라는 말이 한번 툭 튀어나왔다 ㅎㅎ
짧지만 그래도 고민을 조금 했던 문제기 때문에 작성해놓음! 
실버2답게, 그리고 그리디 답게 풀이를 생각해내는 순간 그닥 어렵지는 않았다~

 

⚫️ 문제

https://www.acmicpc.net/problem/11501

11501번: 주식

 

⚫️ 풀이

1️⃣ 첫번째 시도

시간초과가 났다. 제출 시간 보면 1분전이라고 뜨는데 ㅋㅋ 1분동안 천천히 채점하더니 88%에서 시간초과가 났다. 아무래도 데이터가 N이 100만까지 들어오면 뻑나는 것 같다.

아니, 근데 이거 구현하는데 은근 오래걸렸다. 일단 풀이과정을 좀 보자

고민하다가 찾은 첫번재 풀이 방법이다. 주식은 한개씩만 살 수 있지만 파는건 맘대로 팔 수 있다. 일단 몇개를 갖고 있든 최고 가격으로 파는게 +1 이라도 이득을 보기 때문에, max값을 찾아주자고 판단했다. 그리고, 만약 max값이 중간에 있다면, 그 이후에는 또 주식을 살지 팔지 고민해야한다. 그렇다면, 지금 찾은 max값 이후의 값들 중에서 또 max값을 찾고, 팔아주고 ... 🔁 를 반복해주면 되지 않을까? 

이론상으로는, 내가 원하는 답을 찾을 수 있었다. 그리고, 결국 max값을 찾고 배열을 잘라서 또 살펴보는 것이기 때문에 선형탐색과 시간복잡도가 같을 것이라고 판단했다. N은 총 100만개가 들어올 수 있으므로, 선형탐색의 시간복잡도인 O(n) 과 동일할것이라고 판단했다. 

그래서 구현한 코드는 아래와 같다.

처음에 재귀로 구현하다가 구현이 안되길래 (내 머리의 한계.. 왜 안됐지? ㅋㅋㅋㅋ 일단 빠르게 구현할 수 있는 while문으로 구현햇다.

import Foundation

func solution() {
    let t = Int(readLine()!)!

    for _ in 0..<t {
        let n = Int(readLine()!)!
        var price = readLine()!.split(separator: " ").map{ Int($0)! }
        var answer = 0
        var idx = 0

        while idx < price.count {
            if price.count == 1 {
                break
            }

            let maxNum = price.max()!
            idx = price.firstIndex(of: maxNum)!

            for i in 0..<idx {
                if maxNum > price[i] {
                    answer += maxNum - price[i]
                }
            }

            if idx == price.count - 1 {
                break
            }

            price = Array(price[idx+1..<price.count])
            idx = 0
        }

        print(answer)
    }
}

solution()

 

음.. O(n)으로 구현한다고 해놨지만, 얼떨결에 구현을 마구잡이로 하다보니 O(n^2)으로 구현해놓았더라고.. 그래서인지 100만이 넘어가면 당연히 시간 초과가 나겠지 ㅠㅠ 다른 구현방법을 찾아보아야한다. 

2️⃣ 두번재 시도 - while문을 없애고 구현한건 아래 코드.

import Foundation

func solution() {
    let t = Int(readLine()!)!

    for _ in 0..<t {
        let n = Int(readLine()!)!
        var price = readLine()!.split(separator: " ").map{ Int($0)! }
        var answer = 0

        var maxNum = price.max()!

        for i in 0..<price.count {
            if price[i] < maxNum {
                answer += maxNum - price[i]
            } else if price[i] == maxNum {
                if i == price.count - 1 {
                    break
                }
                maxNum = Array(price[i+1..<price.count]).max()!
            }
        }

        print(answer)
    }
}

solution()

아 이것도, 이전 첫번쨰 코드와 동일하게 1분정도 채점을 하더니 83%에서 시간초과가 났다. ㅋㅋㅋㅋ 아오 채점 기다리는거 심장떨려.. 그나저나 여기서 내가 간과한게 하나 있었다. 바로,,, Swift 배열에서 max()값을 찾는 매서드가 바로 O(N)이라는 사실. ㅠㅠㅠ 그래서 결국 이렇게 풀더라도, n개의 for문을 돌지만, for 문 내부에서 O(N)씩 max값을 찾아주므로, O(N^2)이 된다 ...... 하....... 이렇게 푸는 방법이 아니란 말인가 ㅠㅠ 

지난번에 친구랑 이야기할때, 이렇게 풀었는데 시간초과가 난다면, 풀이 과정 자체가 잘못 된거다 라고 이야기 나눈적이 있는데..ㅋㅋㅋ 내가 풀이하는 방식이 잘못됐나 싶다. ... 흠.. 다시 고민해보자. ㅠㅠ 하 ... 쉬운문제인거같은데 왤케 고민하고있는거지 ;; 실버2라고 고작!!!!

 

알았다. 알았다. 알았다!! 내가 푼 방식은 틀리지 않았고, 구현하는데서 조금 더 고민이 필요했다. 주어진 주식의 가격 (내가 price라고 변수 만들어놓은것)의 순서는 바뀌지 않는다. 결국, 최대 이익을 얻기 위해서는, 뒤에있는 숫자가 커야, 팔아서 수익을 남길 수 있다. 즉, 배열을 거꾸로 보는 것이다. 현재 -> 과거로 돌아간다고 생각하고, 현재 max가 n원이라면, 앞에있는애를 사고파는게 이득인가?를 생각해보자.

이 과정을 맨 뒤부터 앞까지 반복해보자. 그렇다면, max값을 max()!메서드를 사용해서 찾아줄 필요도 없고, 그냥 하나의 for문으로 if문만을 사용해서 구현이 가능하다. 즉, O(N)의 시간복잡도로 문제를 풀 수 있다

3️⃣ 세번째 시도

위 그림을 그대로 코드로 구현하면 아래와 같다.

import Foundation

func solution() {
    let t = Int(readLine()!)!

    for _ in 0..<t {
        let n = Int(readLine()!)!
        var price = readLine()!.split(separator: " ").map{ Int($0)! }
        var answer = 0

        var maxNum = price[price.count-1] // max초기값 그냥 맨뒤 값으로

        for i in stride(from: price.count-1, through: 0, by: -1) {
            if maxNum < price[i] { // maxnum보다 큰놈을 발견했다면 max를 갱신해줘
                maxNum = price[i]
            } else if price[i] < maxNum {
                answer += maxNum - price[i]
            }
        }

        print(answer)
    }
}

solution()

짜잔~~ 맞았다 후,,, 이 문제푸는데 한시간 반정도? 걸린것 같다. 역시, 풀이가 생각났는데, 구현이 어려우면 진짜 ,,,, 찾기도 힘들고 그렇다 ㅠㅠ 중간에 index문제로 엄청 헷갈려서 헤매기도 했고, 재귀로 구현햇다가 어쩌고 저쩌고 하면서 허탕친 코드도 많았다. 아직,, 구현실력이 많이 부족한 것 같다 ㅠㅠ 

더 열심히 풀어야겠다. 아자아자..... 실버2주제에 나에게 많은 고민을 하게 했네 ...... 하... 배열을 거꾸로 돌려서 시간복잡도가 확!! 줄어드는 풀이가 생각보다 많은 것 같으니까, 잘 생각해두자.