728x90
반응형
그리디 문제이다. 살짝 어려웠다. 난 2가지 방식으로 풀었는데, 의문점이 있다.
import sys
input = sys.stdin.readline
"""
1. 큰 값 순서대로 정렬
2. 현재 가장 큰 값 기준으로, 원본 리스트 역순 순회하며 가장 큰 값 찾기
3. 찾았다면, 가장 큰 값 포함한 좌측 값 전부 사서 큰값에 팔기
4. 원본리스트에서 방금 사용된 값을 전부 없애기
5. 반복
현재 가장 큰 값 idx가 while문당 1씩 증가하는데, 이거 좀 비효율이다. 이후에 올 큰값들이 지워지면 쓸모없어지기 때문
따라서 가장 큰 값 리스트에서도 값들을 지워주고, 항상 0으로 인덱싱 하면 될 것 같은데 귀찮다.
[1, 3, 1, 10, 2, 9, 3, 10, 5]
[10, 9, 5, 3, 2, 1]
"""
for _ in range(int(input())):
N = int(input())
values = list(map(int, input().split()))
# 중복제거 후 최댓값 순 정렬하기
sorted_values_set = set(values)
sorted_values = sorted(list(sorted_values_set), reverse=True) # 최댓값 리스트
# 원본 리스트가 빌 때까지 진행
result = 0
cur_max_idx = -1
while values:
cur_max_idx += 1
# 뒤쪽부터 탐색
for i in range(len(values) - 1, -1, -1):
# 최대값 만난 경우 좌측 것들 다 사서 최대값에 팔기
cur_max = sorted_values[cur_max_idx]
if values[i] == cur_max:
sell_values = values[:i + 1] # 팔고 나서 삭제할 값들
values = values[i + 1:] # 팔고 남은 값들 (이어서 계산할 애들)
# 이득 계산
for v in sell_values:
result += (cur_max - v)
break
print(result)
최댓값 순서로 정렬된 리스트를 가지고, 원본 리스트를 우측부터 순회해서 좌측에 있는 주식을 모두 판다.
이렇게 하면 안전하게 최적의 값을 얻을 수 있지만 복잡도가 O(N^2) 정도 된다. 슬라이싱 때문에.
어떻게 하면 최적화할 수 있을까 고민해 보다가 아래와 같이 최적화했다.
import sys
input = sys.stdin.readline
for _ in range(int(input())):
N = int(input())
values = list(map(int, input().split()))
result = 0
cur_max = 0
for i in range(N - 1, -1, -1):
if values[i] > cur_max:
cur_max = values[i]
else:
result += (cur_max - values[i])
print(result)
기존보다 훨씬 간단한 코드다. 시간복잡도는 O(N) 이다.
리스트를 우측부터 단 한번 순회하며 최적의 값을 얻어낸다.슬라이딩도, 복잡한 조건문도, while도 2중 for문도 다 없다.
이론상 완벽하게 원래 코드보다 빠른 상위호환 코드다.
뒤쪽부터 순회하며 최댓값을 저장해 두고, 해당 값보다 다음 값이 작으면 바로 팔아 버리면 된다. 이렇게 해도 문제가 없다는 걸 처음에는 몰랐었다.
그런데 결과가 이상하다.
2번째, 3번째 제출 코드가 O(N) 코드다. 시간이 각각 3256, 3088인데 기존 내 코드보다 비슷하거나 오히려 더 느리다..
아무리 생각해도 이유를 모르겠다. 기존 내 코드보다 덜어내면 덜어냈지 더 한게 아예 없는데 대체 어째서? 심지어 메모리도 더 먹는다. 테스트 케이스가 특이한 건가....
어쨌든, O(N) 코드가 더 효율적인 건 명백하다. 백준 테스트 케이스의 문제 같은데.. 뭐, 어떤 코드가 더 나은 코드인지 파악만 하고 가도록 하자.
728x90
반응형
'Algorithm > Greedy' 카테고리의 다른 글
[백준 20310 / Python / 실버3] 타노스 (0) | 2025.07.04 |
---|---|
[백준 19941 / Python / 실버3] 햄버거 분배 (0) | 2025.06.30 |
[Baekjoon 11000 / Python / 골드5] 강의실 배정 (0) | 2025.01.23 |
[Baekjoon 2138 / Python / 골드4] 전구와 스위치 (2) | 2024.09.26 |
[Baekjoon 1911 / Python / 골드5] 흙길 보수하기 (0) | 2024.08.19 |