백준 그리디 Greedy 문제 11501 주식, swift 문제풀이

 

 

 

---

백준 11501번, 주식 문제설명

오늘 풀어볼 백준 11501번, 주식문제는 solved.ac 기준, 실버2의 난이도를 가진 문제입니다.

일반 코딩테스트 기준, 중반대에 나올 수 있는 문제라고 볼 수 있겠습니다.

 

 

 

 

시간제한은 5초입니다. 보통은 1, 2초가 주류인데 특이한 경우네요. 메모리제한은 256MB입니다.

문제 설명을 이어서 보도록 하겠습니다. 

 

 

 

해당문제는 한 라인에 주식의 가격이 주어질때 최대한 큰 수익을 낼 수 있도록 하는 것입니다. 주식 매매에 있어서 할 수 있는 행동은 크게 3가지입니다. 

1. 주식 하나를 산다. (현재 가격의 주식 1개 매수)

2. 원하는 만큼 가지고 있는 주식을 판다. (원하는 갯수의 주식을 현재 가격에 매도가능)

3. 아무것도 안한다.

 

주식을 가장 효율적으로 매수, 매도할 수 있는 방법은 무엇이 있을까요? 

이어서 문제 입출력 예시를 알아보겠습니다. 

 

 

 

 

본 문제는 여러개의 테스트케이스가 존재할 수 있습니다. 가장 첫 줄에 T가 입력되고, T번의 케이스에 대해 최대 이익을 출력하면 됩니다. 주식 날의 수를 나타내는 자연수 N의 범위는 백만이므로, O(N^2) 미만의 시간복잡도를 고려해봐야 겠습니다.

 

이어서 문제 예시를 보도록 하겠습니다.

 

예시 1) 예를들면 첫번째 케이스는 3일의 기간 동안의 최대 이익을 계산하면 됩니다. 아쉽게도 1번째 케이스는 어떠한 경우로도 수익을 낼수가 없습니다. 매수한 주식을 더 비싸게 살 수 있는 경우가 존재하지 않죠.

예시 2) 두번째 예시는 좀 다릅니다. 1, 2번째 날의 주식 2개를 총 8원에 사고, 마지막 날에 9원에 모두 팔면 8원의 투자로 18원의 이익, 순수익이 10원이 됩니다. 

 

이 문제는 주식의 가격을 역순으로 순회하면서 최대 주식의 가격을 체크하고, 최대 주식 가격보다 작은 경우에는 매수했다고 가정하고 순수익을 누적시켜주면 됩니다. 요약하자면 아래와 같습니다. 

 

1) 역순 순회를 하면서 최대 가격이 나오면 최댓값을 갱신한다.

2) 현재까지 나온 최대 가격보다 낮은 가격이 나오면 매수했다고 가정하고 순수익을 누적시킨다. (현재 순회하는 가격에서 매수한 뒤, 최대 가격에 왔을때 매도했다고 계산하게 됩니다.)

 

이제 swift언어로 해당 문제를 풀어보도록 하겠습니다. 

 

 

 

---

백준 11501번, 주식 swift 문제풀이
swift 입력함수 구현

본 문제의 시간제한은 5초이지만 보다 효율적인 실행시간에 문제를 풀기 위해 입력 최적화 함수를 작성해두었습니다. 백준알고리즘 문제는 간혹 swift에 대한 시간보정이 되어있지 않아서 요즘은 이렇게 풀고 있습니다. 

 

2행) ip는 단순 정수를 입력받는 문제로, 이건 최적화라기 보단, 이후 입력을 다수 사용할때 보다 간결해 보이도록 하는 목적이 큽니다. 

3 ~ 17행) ip2는 입력 최적화를 적용한 함수로, 1라인 입력값으로부터 공백 단위로 정수를 모아 [Int]타입의 배열로 반환해줍니다.

 

 

 

 

 

19행) 해당 문제의 테스트케이스, T를 입력 해줍니다. 

 

 

 

---

역순으로 주식의 가격을 순회, 최대 이익을 구하자

21행) 그 다음, 주식의 날 수를 입력받는데요. swift언어의 입력방식 특성 상, 본 문제에서는 N을 굳이ㅣ 입력 받을 필요가 없어서 저렇게 사용할 수 있음을 예시로 보여드립니다. 

 

22행) 이제 주식 가격 리스트를 받아서 arr에 저장해줍니다. 

23 ~ 24행) 이제 주식의 가격을 역순으로 순회하면서 기록한 최대 가격은 mx, 현재까지의 누적 수익은 profit에 저장합니다. 

25 ~ 32행) 앞서 말했던 주식가격을 역순으로 봄면서 최대 수익을 연산하는 구간입니다. 앞서 사용하기로 한 규칙을 다시 적어보겠습니다.

 

1) 역순 순회를 하면서 최대 가격이 나오면 최댓값을 갱신한다.

2) 현재까지 나온 최대 가격보다 낮은 가격이 나오면 매수했다고 가정하고 순수익을 누적시킨다. (현재 순회하는 가격에서 매수한 뒤, 최대 가격에 왔을때 매도했다고 계산하게 됩니다.)

 

역순 순회를 하면서 최대 가격이 나오면 mx에 갱신을 해주고, 만약 최댓값이 아니라면, profit에 mx - num을 누적시켜줍니다..

-> num원에 매수해서 mx값에 매도한 수익을 profit에 누적한다고 생각하면 좀더 이해하기 쉬울 것 같습니다. 

이렇게 누적해 놓은 수익, profit을 각 케이스마다 출력해주면 끝입니다.

 

위의 코드에서는 arr.reviersed().forEach { ... } 로 역순 순회를 했지만, while문 등으로 역순 순회를 해도 크게 문제는 없습니다. while문으로 역순 순회를 하는 예시는 아랫 코드를 참고하시기 바랍니다.

 

 

 

 

 

 

 

 

---

이렇게 오늘은 그리디 문제, 백준 11501 주식 문제를 풀어봤습니다.

그리디 유형의 문제는 초반 접근 방식부터 전체적으로 어려운 것 같습니다.. 방법은 많이 풀어보는 방법이 아닐까 싶네요. 😊

 

본 문제, 백준 11501번 주식문제의 swift언어 제출 결과는 아래와 같습니다. 😎

 

 

 

 

 

 

 

백준 11501 주식 swift 문제풀이 제출 결과