[BOJ_11501] 주식

 

📌 문제 링크: https://www.acmicpc.net/problem/11501

11501번: 주식

 

❌ 내 풀이(Failure) -1:

91%에서 시간 초과

 

❌ 내 풀이(Failure) -2:

코드를 조금 수정했지만 여전히 91% 시간 초과

 

✅ 내 풀이(Success) :

구글링을 통해 학습한 풀이로 핵심은 뒤에서부터 계산하기!

 

🧐 Review:

 처음 생각했던 풀이는 주식의 가격이 최대일 때 보유한 주식을 팔고, 남은 주식들 중에서 주식의 최댓값을 갱신한 뒤 같은 방법을 이용해서 결과를 구하는 방식이었다. 하지만 이 방법은 N의 최댓값이 1,000,000으로 매우 큰데, for반복문과 sum() 함수, max() 함수를 함께 이용해서 시간 복잡도가 O(N^2)까지 올라가기 때문에 시간 초과가 발생할 수밖에 없다. 그래서 어떻게 하면 시간 복잡도를 줄일 수 있을지 고민해보다가 일단 sum() 함수를 이용한 부분을 수정해서 제출해봤다. 하지만 여전히 max() 함수를 이용하기 때문에 시간 복잡도는 O(N^2)이라서 시간 초과가 발생했다.

 제출했던 두 번의 결과가 시간초과로 틀리자 더 이상 내 코드를 최적화하기보단 다른 사람의 풀이를 참고해서 배우자라는 생각으로 구글링을 통해 풀이를 찾았다. 참고했던 풀이는 주식을 사고파는 것을 배열의 앞에서부터 진행하는 것이 아니라 뒤에서부터 탐색하는 과정을 이용했다. 이렇게 코드를 작성한다면 주식의 최댓값을 매번 배열의 남은 모든 원소들 중에서 미리 찾지 않아도 되기 때문에 시간 복잡도를 O(N)으로 줄일 수 있다.