[SWEA] D2 1859. 백만 장자 프로젝트 문제 풀이

BOJ는 백준 허브를 통해서 자동으로 GITHUB에 업로드 되지만,

 

SWEA는 별도의 자동 업로드 프로그램이 없어서 블로그에 정리합니다.

 

근데 처음 푸는데 첨부터 시간초과 뜸 ( 슬픔 )

---

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LrsUaDxcDFAXc 

SW Expert Academy

---

🤔1트 ( 무지성으로 일단 적기 )

# import sys
# input = sys.stdin.readline

n = int(input())
price = []

for k in range(n):
    day = int(input())
    price = list(map(int,input().split()))
    answer = 0
    
    for i in range(len(price)):
        if price[i] == max(price):
            price[i] = 0
        elif price [i] < max(price):
            answer += max(price) - price[i]

    num = str(k+1)
    print(f'#{num} {answer}')

1개 빼고는 모두 시간초과

반복문 2 + 조건문 1... 내가 봐도 무겁기는 하다

 

---

🙄 2트 ( popleft 써서 효율 좋게 만들기)

# import sys
# input = sys.stdin.readline
from collections import deque

n = int(input())

for k in range(n):
    day = int(input())
    price = deque(list(map(int,input().split())))
    answer = 0
    
    while price:
        if price[0] == max(price):
            price.popleft()
        elif price [0] < max(price):
            answer += max(price) - price[0]
            price.popleft()


    num = str(k+1)
    print(f'#{num} {answer}')

그래도 7개로 늘어났다.

---

🤪3트 ( 뭐가 문제일까? )

시간문제는 해결된것 같아서 찾아보니 이런 댓글이 있었다.

long long형 변수 = long long형 변수 + int형 변수*int형 변수 로 할때, 'int형 변수*int형 변수'의 계산값이 표현할 수 있는 범위는 int의 표현범위와 같기 때문에 실제 곱한 값이 int 범위 밖이면 우리가 원하던 값이 아니게 됩니다. 전 알고리즘은 맞았는데 이 부분을 고려하지 못해서 10개중 7개의 테스트 케이스만 맞더라고요. 어디서 틀렸는지 고민하는데 꽤 오래 걸렸어서 혹시 저랑 비슷한 상황에 처하신분들 있으면 도움이 됬으면 하네요 ㅎㅎ

하지만 이건 JAVA나 C에 해당되는 내용이고 Python은 Integer = ( int + long ) 오버플로우가 발생하지 않는다.

거꾸로 강을 거슬러 오르는 저 힘찬 연어들처럼~

이런 댓글이 있길래, 거꾸로 하면 시간 효율이 좋아질까 해서 reverse 후에  popleft를 써봤다

# import sys
# input = sys.stdin.readline
from collections import deque

n = int(input())

for k in range(n):
    day = int(input())
    price = deque(list(map(int,input().split())))
    price.reverse()
    max = price[0]
    answer = 0
    
    while price:
        if price[0] >= max:
            max = price[0]
            price.popleft()

        elif price [0] < max:
            answer += max - price[0]
            price.popleft()
    
    num = str(k+1)
    print(f'#{num} {answer}')

통과!

 

---

아직도 블루투스 이어폰이 없냥? 나를 누르면 주겠다 냐옹!