BOJ/Swift

백준 17939번 Gazzzua 파이썬

띵지니어 2024. 6. 3. 10:41
반응형

https://www.acmicpc.net/problem/17939

 

내 코드

N = int(input())
coin = list(map(int, input().split()))[::-1]
standard = coin[0]
result = 0
for i in range(1, len(coin)):
if standard > coin[i]:
result += standard - coin[i]
else:
standard = coin[i]
print(result)

 

Review

문제에 나와있는 핵심 조건은 아래와 같습니다.

1. 구매는 매 분마다 1개씩 가능
2. 판매는 제한 없음

문제에 나와 있는 예제 1 5 10 2 4 3으로 설명하겠습니다.

언제 사고 언제 파는지에 대한 기준을 정해야 한다고 생각을 했습니다.

하지만 그냥 보면 아무것도 생각 안 나서.. 뒤집어 보겠습니다

3 4 2 10 5 1

이렇게 봤을 때, 생각나는 논리가 있었습니다.

현재 index 기준으로 오른쪽에 있는 것 중에 자기 보다 가격이 낮은 것까지 체크를 하여 수익을 계산하면 된다.
자기보다 크다면 기준을 변경하여 위 내용을 반복합니다.

그림으로 보면 아래와 같습니다.

 

이렇게 구현을 하면 시작 복잡도는 O(N)이 나오게 됩니다.
처음에는 while 문으로 풀었는데 가독성 면으로도 for문이 훨씬 괜찮은 것 같습니다.

아래는 Swift 언어 + while 문입니다.

import Foundation
let N = Int(readLine()!)!
let arr = readLine()!.split(separator: " ")
.compactMap { Int($0) }.reversed()
.map { Int(String($0))! }
var index = 0
var result = 0
var standard = arr[0]
while N - index > 1 {
if standard > arr[index + 1] {
result += (standard - arr[index + 1])
} else {
standard = arr[index + 1]
}
index += 1
}
print(result)
반응형
목차(index)