[Swift 알고리즘] 백준 2798 블랙잭

백준 2798번 <블랙잭>

브루트 포스 예제 1단계

 

메모리 69104KB / 시간 8ms

let input = readLine()!.split(separator: " ").map{ Int($0)! }
let n = input[0], m = input[1]
let cards = readLine()!.split(separator: " ").map{ Int($0)! }
print(blackJack(n,m,cards))

func blackJack(_ n: Int, _ m: Int, _ cards: [Int]) -> Int{
    var maxSum = 0
    for i in 0..<n {
        for j in i+1..<n {
            for k in j+1..<n {
                let sum = cards[i] + cards[j] + cards[k]
                if sum <= m && maxSum < sum {
                    maxSum = sum
                }
            }
        }
    }
    return maxSum
}

첫번째 부터 카드 세 장을 차례로 뽑도록 반복문을 세 번 돌려, 세 수의 합이 m보다 작거나 같고 기존 maxSum 보다 클 경우 maxSum으로 저장하도록 하였다. 

 

 

1차 시도 : 메모리 72232KB / 12ms

뽑은 카드 세 장의 합을 저장하는 배열을 따로 만들어 조건에 부합할 경우 하나씩 배열에 추가해, 마지막에 .max() 로 최대값을 반환하도록 하였다. 최대값 하나만 필요한 세 수의 합을 굳이 배열에 다 저장하면서 메모리 낭비를 할 필요는 없기에 비효율적이라 생각함.

var sum = [Int]()
..
            if i < j, j < k, cards[i] + cards[j] + cards[k] <= m {
                sum.append(cards[i] + cards[j] + cards[k])
...
return sum.max()!

2차 시도 : 메모리 69104KB / 12ms

배열 대신 maxSum(최대 합) 변수를 선언해준 후, 합이 더 큰 경우만 저장한다. 

var maxSum = 0
for i in 0..<n {
    for j in 1..<n {
        for k in 2..<n {
            let sum = cards[i] + cards[j] + cards[k]
            if i < j, j < k, sum <= m, maxSum < sum{
                maxSum = sum
...
return maxSum

 

3차 시도 

i < j, j < k 조건을 따로 둘 필요없이, for문을 돌릴 때 다음과 같이 j는 i+1로 시작하고 k는 j+1로 시작하도록 해주면 더 빠르게 해결할 수 있다. 

for i in 0..<n {
    for j in i+1..<n {
        for k in j+1..<n {