Algorithm/Greedy

[백준 11501 / Python / 실버2] 주식

양선규 2025. 7. 11. 22:04
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문도 다 없다.

이론상 완벽하게 원래 코드보다 빠른 상위호환 코드다.

 

뒤쪽부터 순회하며 최댓값을 저장해 두고, 해당 값보다 다음 값이 작으면 바로 팔아 버리면 된다. 이렇게 해도 문제가 없다는 걸 처음에는 몰랐었다.

 

그런데 결과가 이상하다.

 

왜 O(N)이 더 느리지

 

2번째, 3번째 제출 코드가 O(N) 코드다. 시간이 각각 3256, 3088인데 기존 내 코드보다 비슷하거나 오히려 더 느리다..

아무리 생각해도 이유를 모르겠다. 기존 내 코드보다 덜어내면 덜어냈지 더 한게 아예 없는데 대체 어째서? 심지어 메모리도 더 먹는다. 테스트 케이스가 특이한 건가.... 

 

어쨌든, O(N) 코드가 더 효율적인 건 명백하다. 백준 테스트 케이스의 문제 같은데.. 뭐, 어떤 코드가 더 나은 코드인지 파악만 하고 가도록 하자.

728x90
반응형