[파이썬] SWEA: 백만장자 프로젝트 / 탐색 방향에 따른 비교

문제

25년 간의 수행 끝에 원재는 미래를 보는 능력을 갖게 되었다. 이 능력으로 원재는 사재기를 하려고 한다.
다만 당국의 감시가 심해 한 번에 많은 양을 사재기 할 수 없다.
다음과 같은 조건 하에서 사재기를 하여 최대한의 이득을 얻도록 도와주자.
    1. 원재는 연속된 N일 동안의 물건의 매매가를 예측하여 알고 있다.
    2. 당국의 감시망에 걸리지 않기 위해 하루에 최대 1만큼 구입할 수 있다.
    3. 판매는 얼마든지 할 수 있다.
예를 들어 3일 동안의 매매가가 1, 2, 3 이라면 처음 두 날에 원료를 구매하여 마지막 날에 팔면 3의 이익을 얻을 수 있다.

[입력]
첫 번째 줄에 테스트 케이스의 수 T가 주어진다
각 테스트 케이스 별로 첫 줄에는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고,
둘째 줄에는 각 날의 매매가를 나타내는 N개의 자연수들이 공백으로 구분되어 순서대로 주어진다.
각 날의 매매가는 10,000이하이다.

[출력]
각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고, 최대 이익을 출력한다.

[예제 풀이]
1번째 케이스는 아무 것도 사지 않는 것이 최대 이익이다.
2번째 케이스는 1,2일에 각각 한 개씩 사서 세 번째 날에 두 개를 팔면 10의 이익을 얻을 수 있다.

---

23.04.05 추가

많은 풀이들이 뒤부터 탐색하는 이유를 깨달았다.

 

1. 앞부터 탐색하는 경우

(시작 ~ 처음 최댓값 index) 범위에서 구매 및 판매

(처음 최댓값 index+1, 끝범위)에서 다시 재귀함수처럼 최댓값 찾고, 다시사고, 그 다음 범위에서 또 함수..

이렇게 하면 안좋은 점이 10 9 8 7 6 5 4 3 2 1 처럼 역순이면 O(n^2)이다.

 

2. 뒤부터 탐색하는 경우

맨 뒤의 원소를 max로 두고, 계속 뒤부터 보면서 max보다 작으면 이득을 보고 판 것처럼 처리한다.

그렇지 않으면 max값을 바꿔준다. 시간 복잡도는 O(n).

# 테스트 케이스의 입력
N = int(input())

for j in range(N):
  # 출력에 필요한 값 입력
  n = int(input())
  li = list(map(int, input().split()))

  #역순으로 보기위해 리스트를 뒤집음
  r = list(reversed(li))
  idx = r[0]  
  profit = 0 
  
  for i in r:
    if i < idx:
      profit += idx - i
    elif i > idx:
      idx = i
      
  print("#"+str(j+1), profit)

---

기존풀이

1. 매매가 예측값을 리스트로 입력받는다

2. 가장 큰 수의 인덱스를 받아 해당 일자까지의 수익을 answer에 누적

3. 리스트를 그 다음 일자부터 끝까지로 초기화

4. 리스트가 빌 때 까지 반복

T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
cnt=1
for test_case in range(1, T + 1) :
    n=int(input())
    a=list(map(int, input().split()))
    answer=0
    
    while len(a)>0 :
    	amax=max(a)
        maxidx=a.index(amax)
        answer+=(amax*maxidx)-sum(a[ : maxidx]) 
        # 매매가 예측값이 가장 큰 일자까지의 수익금 정산
        a=a[maxidx+1 : ] 
        # 그 뒤로 남은 일자에서 가장 큰 예측값을 또 찾도록 반복
	
    print(f'#{cnt} {answer}')
    cnt+=1

 

point 1 리스트에서 가장 큰 수의 인덱스를 받아오는 방법은 두 가지가 있다.

첫번째는 max()함수와 index()함수를 사용하는 것

a=[1,2,3,4,5]
a.index(max(a))

Out: 4

두번째는 numpy의 argmax를 사용하는 것

import numpy
a=[1,2,3,4,5]
numpy.argmax(a)

Out: 4

point 2 인덱스 n 앞에 있는 원소는 n개(0번부터 n-1번까지)이다.

point 3 sum(list[ : n])은 0번부터 n-1까지의 합을, sum(list[n : ])은 n번부터 끝까지의 합을 반환한다.

 

SW Expert Academy