* 백준 11501번 - 주식

Gyuhan Park·2021년 11월 23일
0

코딩테스트 정복

목록 보기
30/47

홍준이는 요즘 주식에 빠져있다. 그는 미래를 내다보는 눈이 뛰어나, 날 별로 주가를 예상하고 언제나 그게 맞아떨어진다. 최대 이익이 얼마나 되는지 계산하시오.

# 틀린 코드

3가지 행동을 if문으로 나눴다. 다음 주가가 떨어지는데 주식이 없으면 아무것도 안한다. 주식이 최고가면 판다. 최고가가 아니면 무조건 산다. 최고가 이후에 팔 기회가 생기면 판다. 논리상 별 문제 없어보이는데 틀렸다. 반례가 있는 것 같은데 특별히 찾지 못했다. 다른 방법은 없을까? if문이 좀 지저분하기도 해서 다시 생각해보았다.

import sys
input = sys.stdin.readline

T = int(input())
for _ in range(T):
  N = int(input())
  stock = list(map(int, input().split()))
  benefit = 0
  count = 0
  price = 0
  maxPrice = max(stock)
  maxPriceIndex = stock.index(maxPrice)
  for i in range(len(stock)-1):
    if stock[i] > stock[i+1] and count == 0: # 아무 것도 안한다
      continue
    elif stock[i] == maxPrice: # 최고가에 판다
      benefit += count * (stock[i] - price/count)
      count, price = 0, 0
    elif stock[i] > stock[i+1] and i > maxPriceIndex:
      benefit += count * (stock[i] - price/count)
      count, price = 0, 0
    else: # 최고점 아니면 풀매수
      count += 1
      price += stock[i]
    
  if count:
    benefit += count * (stock[-1] - price/count)
  
  print(int(benefit))

# 정답 코드

이 방법은 최댓값도 계산해놓지 않는다. 뒤에서부터 오면서 최댓값을 찾아간다. 꼭 최댓값이 아니더라도 다음값보다 크다면 차익실현한다. 주가가 오른 경우와 같다. 최댓값과 현재주가를 뺀 값을 쭉 더해주면 최댓값에서 매수한 모든 주식을 판 것과 같은 결과를 만든다.
반복문을 뒤집은 것만으로 코드가 간단해질 수 있다는 게 신기하다. 역시 아이디어 싸움!!!! 순서가 중요한 경우 정렬을 안쓰는데 뒤에서부터 반복문 도는 방법도 떠올리자!

import sys
input = sys.stdin.readline

T = int(input())
for _ in range(T):
  N = int(input())
  stock = list(map(int, input().split()))
  benefit = 0
  maxPrice = 0

  for i in range(len(stock)-1, -1, -1):
    if stock[i] > maxPrice:
      maxPrice = stock[i]
    else:
      benefit += maxPrice-stock[i]
    
  print(int(benefit))
profile
단단한 프론트엔드 개발자가 되고 싶은

0개의 댓글