반응형
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)
반응형
'BOJ > Swift' 카테고리의 다른 글
[프로그래머스] 가장 먼 노드 Swift (1) | 2024.11.13 |
---|---|
백준 3020번 개똥벌레 Swift (0) | 2024.11.08 |
백준 2579번 계단 오르기 Swift (0) | 2024.05.13 |
백준 2609번 최대공약수와 최소공배수 Swift (0) | 2024.04.18 |
백준 2407번 조합 Swift (0) | 2024.04.17 |