[SWEA] 1859. 백만 장자 프로젝트

1️⃣ 답안

T = int(input())
answer = []

for i in range(T):
  N = int(input())
  price = list(map(int, input().split()))
  price.reverse()
  max = price[0]
  tmp = 0
  for j in range (1, N):
    if price[j] > max:
      max = price[j]
    elif price[j] < max:
      tmp += max - price[j]
  answer.append(f"#{i + 1} {tmp}")      
  
# 답안 출력
print("\n".join(answer))

2️⃣ 풀이

매매가들을 입력 받은 뒤, 이를 리스트 형태로 저장하고 revere()를 통해 역순으로 만든다.. 그 이후 가장 첫 번째 값을 max 변수에 저장하고 순회하면서 값이 더 크면 max 값을 갱신, 값이 작으면 max와의 차이를 tmp 변수에 계속 더하면서 저장한다. 순회가 끝나면 이를 answer 리스트에 알맞은 출력 문자열 형태로 저장한다. 모든 과정이 끝나면 출력한다.

3️⃣ 후기

⚠️ 문제점

처음에는 가격 리스트를 앞에서 부터 순회하면서, 최대값은 max()와 index()를 통해 알아내려고 했다. 그러나 반복적으로 max()와 index()를 사용하게 되면서 시간 복잡도가 O(N^2)로 증가하였다.

💡 해결

이를 해결하기 위해 리스트를 reverse()를 통해 뒤집은 다음 순회하였다. 이 과정을 사용하면 총 리스트를 1번만 순회하면 되기 때문에 시간 복잡도가 O(N)으로 감소한다.

---

❌ 실수

for 문을 총 2번 사용했는데, 두 반복문에서 변수를 동일하게 i로 사용해서 문제가 된 적이 있었다. 간단한 내용이지만 주의하도록 하자.

---

⭐️ 개선할 내용

• max(), index() 등의 내장 함수들을 사용할 때 각각의 시간 복잡도에 대해서 알아두어 코드의 시간 복잡도를 계산할 수 있도록 하자.
• 리스트를 항상 앞에서부터 조회한다는 고정 관념을 버리자. reverse()를 통해 리스트를 뒤집거나, 슬라이싱을 통해 필요한 부분만 조작하는 등 다양한 관점에서 생각하자.