[sw expert acadmey] 1859. 백만 장자 프로젝트

https://swexpertacademy.com/main/main.do

SW Expert Academy

 

이 문제 진짜 ;;; ㅋㅋㅋㅋㅋ

괜히 lv2 정답율 최하 문제가 아니다.

input 파일이 정말 말도 안되게 길다.

엄청 많은 데이터가 입력되는 문제다.

 

 

원래는 아래와 같이 풀려고 했다.

숫자 다 받아서 map,list로 묶어줌

→ list에서 max 찾고 그 지점까지 원소들을 다 지워주는 함수 만듦

→ 그리고 빈 리스트가 될 때까지 함수 무한반복

 

그래서 만들었다.

def find_max(b):
  for i in range(arr.index(max(arr))+1):
    b+=(max(arr) - arr[0])
    del(arr[0])
  return b

T=int(input())
for t in range(1,T+1):
  N =int(input())
  arr=list(map(int,input().split()))
  profit=0
  while True:
    profit = find_max(profit)
    if arr== []:
      break
  print('#{} {}'.format(t,profit))

이거 10개의 테스트 중에 7개는 맞는다.

근데 8번째부터는 데이터 크기가 어마어마하게 커지기 때문에 '제한시간 초과' 에러가 뜬다.

 

다른 방법을 찾아야했다.

댓글을 보는데 뒤에서부터 풀어야한다는 이야기가 많았다.

근데 어떻게 뒤에서부터 푸는지 감이 안 왔다...

문제를 거꾸로 생각하라는 뜻인지, 인덱싱을 뒤에서부터 하라는 의미인건지.

 

한참을 고민하다가 모범답안을 봤다.

여기서 모범답안이란 python으로 푼 답들 중 실행시간이 제일 짧은 답을 의미한다.

 

모범답안 (박주윤_0715755)

• 202,440 kb메모리
• 873 ms실행시간

T = int(input())
for test_case in range(1, T + 1):
    inputa = int(input())
    inputb = input()
    ls = [ int(i) for i in reversed(inputb.split(' ')) ]
    max = 0
    sum = 0
    for i in ls:
        if max<i:
            max=i
        sum+=max-i
         
    print(f'#{test_case} {sum}')

진짜 이마를 탁 쳤다.

뒤에서 풀라는 게 이런 의미였다니..

어차피 가장 큰수,..... ,두번째로 큰 수,..... ,세번째로 큰 수, ..... 이렇게 배열된다.

이걸 reverse하면 max를 계속 업데이트하며 max에서 그 원소만큼을 계속 sum에 더해주면 된다.

이런게 생각의 전환일까?

정말정말 대단하다.

 

 

 

이렇게 이해를 마치고 나서 모범답안을 보지 않고 스스로 코드를 짜봤다.

• 250,964kb메모리
• 1,101ms실행시간

T = int(input())
for t in range(1,T+1):
    N =int(input())
    arr=list(map(int,input().split()))
    profit=0
    max = 0
    for i in range(N-1,-1,-1):
        if arr[i]> max:
            max = arr[i]
        profit += max - arr[i]
    print("#{} {}".format(str(t),str(profit)))

원리는 모범답안과 다르지 않다.

다만 reverse를 하지 않고 index로 뒤에서부터 인덱싱 해줬다.

 

근데 메모리, 실행시간을 비교해보면 reverse를 하고 원소 하나하나로 for문을 작성하는게 메모리나 실행시간면에서 더 효율적인 것 같다.

 

 

정말 어려웠던 문제다.