알고리즘 문제 - 백준 - 1715 (카드 정렬하기)

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

 

정렬되어 있는 카드 묶음을 모두 합치는 최소 비교 횟수를 구하는 문제

카드의 개수가 적은 묶음부터 2개씩 합치면 최소한의 비교로 구할 수 있음

 

예를들어

10, 20, 40개의 카드를 가진 묶음이 있다면

10장과 20장을 합친 뒤, 합친 30장 묶음과 40장 묶음을 합치면 100번의 비교가 필요함

(10 + 20) + (30 + 40)

 

그럼 카드의 개수가 작은 순서대로 정렬 후 두 묶음의 개수 합과 다음 묶음 개수의 합을 하면 될까?

50, 60, 70, 80 으로 예를 들면

 

순서대로 두 묶음 씩 합칠 때

(50 + 60) = 110

(70 + 110) = 180

(80 + 180) = 260

→ 총 550번의 비교가 필요함

 

하지만, 정답은?

(50 + 60) = 110

(70 + 80) = 150

(110 + 150) = 260

→ 총 520번의 비교로 최소값이 됨

 

두 묶음의 합(110)보다 다음 값(70, 80)이 작다면 작은 값들끼리 합쳐주면 됨

 

 

두 묶음의 합(110)보다 작은 값이 하나라면?

50, 60, 70, 120일 때,

 

순서대로 두 묶음씩 합칠 때

(50 + 60) = 110

(70 + 120) = 190

(110 + 190) = 300

→ 600

 

두 묶음의 합(110) 보다 작은 값이 하나(70)일 때 → 120은 합보다 큼

(50 + 60) = 110

(70 + 110) = 180

(120 + 180) = 300

→ 590

 

따라서, 두 묶음의 합보다 작은 묶음이 있다면, 작은 묶음 순으로 합을 해주는 게 최소값이 됨

→ 문제를 풀고나니.. 바보 같이 풀고 있었다

 

첫 번째 시도

1. 입력 받은 카드 묶음을 카드 개수에 따라 오름차순 정렬
2. 비교 횟수를 저장할 배열을 만듦
3. 이전 묶음의 합과 다음 비교할 카드 묶음을 비교하기 위해 pointer 사용
4. 비교된 카드 묶음은 배열에서 제외하고 비교 횟수 배열에 두 묶음의 합을 넣어줌
5. 카드 배열이 모두 비어질 때까지 반복하고 끝나면, 비교 횟수 배열의 합을 출력

let N = Int(readLine()!)!
var cards = [Int]() // 카드 개수 배열
for _ in 0..<N {
    cards.append(Int(readLine()!)!)
}
cards.sort() // 카드 정렬

var comparisonCount = Array(repeating: 0, count: 100000) // 비교 횟수 배열

var pointer = 1
comparisonCount[0] = cards[0] + cards[1]
cards.removeFirst(2)

while !cards.isEmpty {
    let smallCards = cards.filter{$0 <= comparisonCount[pointer - 1]}
    cards.removeFirst(smallCards.count)
    
    let smallCardsCount = smallCards.count
    if smallCardsCount > 0 {
        for i in stride(from: 0, to: smallCardsCount, by: 2) {
            if i + 1 < smallCardsCount {
                comparisonCount[pointer] = smallCards[i] + smallCards[i + 1]
            } else {
                comparisonCount[pointer] = comparisonCount[pointer - 1] + smallCards[i]
            }
            pointer += 1
        }
    } else {
        let nextCard = cards.removeFirst()
        comparisonCount[pointer] = comparisonCount[pointer - 1] + nextCard
        pointer += 1
    }
}

print(comparisonCount.reduce(0, +))

→ 런타임 에러

1. 카드의 개수 (N)에 따른 분기 처리
   • N의 범위 (1 ≤ N ≤ 100,000)
   • N 카드의 개수가 1이라면, comparisonCount[0] = cards[0] + cards[1] 런타임 에러 발생
2. 비교 횟수 배열을 10000개까지 미리 만들 필요가 없을 것 같음

 

두 번째 시도: 분기처리 및 비교 횟수 배열 수정

let N = Int(readLine()!)!
var cards = [Int]() // 카드 개수 배열
for _ in 0..<N {
    cards.append(Int(readLine()!)!)
}
cards.sort() // 카드 정렬

if N == 1 {
    print(cards[0])
}
else {
    var comparisonCount = [Int]()
    comparisonCount.append(cards[0] + cards[1])
    cards.removeFirst(2)

    while !cards.isEmpty {
        let smallCards = cards.filter{$0 <= comparisonCount.last ?? 0}
        cards.removeFirst(smallCards.count)
        
        let smallCardsCount = smallCards.count
        if smallCardsCount > 0 {
            for i in stride(from: 0, to: smallCardsCount, by: 2) {
                if i + 1 < smallCardsCount {
                    comparisonCount.append(smallCards[i] + smallCards[i + 1])
                } else {
                    comparisonCount.append((comparisonCount.last ?? 0) + smallCards[i])
                }
            }
        } else {
            let firstCard = cards.removeFirst()
            if cards.count > 0 {
                let secondCard = cards.removeFirst()
                comparisonCount.append(firstCard + secondCard)
            } else {
                comparisonCount.append((comparisonCount.last ?? 0) + firstCard)
            }
        }
    }

    print(comparisonCount.reduce(0, +))
}

→ 틀렸습니다

위 방법으로 진행할 경우 위 예시인 50, 60, 70, 80 비교에서

(50 + 60) = 110

(70 + 80) = 150

→ comparisonCount : [110, 150], cards: []

이렇게 되어 바로 comparisonCount의 합 260이 출력됨

110 + 150 비교를 하지 않게 됨

→ 아예 잘못된 방법이었다..

 

세 번째 시도: 이분 탐색 이용

• 카드의 개수가 적은 묶음부터 순서대로 비교하고 두 카드 묶음을 비교한 횟수를 cards 배열에 새롭게 추가하는 방식으로 하면 모두 비교 가능
• cards 배열에 추가할 때는 카드의 순서대로 올바른 위치에 넣어줘야 최소 비교가 가능함
• → 이분 탐색을 이용하여 insert 할 인덱스 위치를 찾아서 사용
• 비교한 카드 묶음은 cards 배열에서 삭제: removeFirst()

let N = Int(readLine()!)!
var cards = [Int]() // 카드 개수 배열
for _ in 0..<N {
    cards.append(Int(readLine()!)!)
}
cards.sort() // 카드 정렬

if N == 1 { // 카드 묶음이 하나일 경우
    print(cards[0])
}
else {
    var count = 0 // 전체 비교 횟수
    while cards.count != 1 { // 카드 배열이 1개일 경우 종료 (비교할 카드가 없기 때문)
        let firstCards = cards.removeFirst()  // 첫번째 카드 묶음
        let secondCards = cards.removeFirst() // 두번째 카드 묶음
        let comparisonCount = firstCards + secondCards // 두 카드의 비교 횟수
        let index = findIndex(comparisonCount) // 삽입할 인덱스 찾기
        
        cards.insert(comparisonCount, at: index) // 새로운 카드 묶음 삽입
        count += comparisonCount // 카드 비교 횟수 추가
    }
    print(count)
}

// 이분 탐색
func findIndex(_ num: Int) -> Int{
    var left = 0
    var right = cards.count - 1
    while left <= right {
        let mid = (left + right) / 2
        if cards[mid] < num {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return left
}

→ 95%에서 틀림

• 카드 묶음이 하나일 경우, 카드 개수를 출력했었다
• 그러나, 카드 묶음 내 카드는 이미 정렬되어 있기 때문에 비교를 하지 않아도 된다
• 따라서 0을 출력하면 됨

 

네 번째 시도: 카드가 하나일 경우 0 출력

let N = Int(readLine()!)!
var cards = [Int]() // 카드 개수 배열
for _ in 0..<N {
    cards.append(Int(readLine()!)!)
}
cards.sort() // 카드 정렬

if N == 1 {
    print(0)
}
else {
    var count = 0
    while cards.count != 1 {
        let firstCards = cards.removeFirst()
        let secondCards = cards.removeFirst()
        let comparisonCount = firstCards + secondCards
        let index = findIndex(comparisonCount)
        
        cards.insert(comparisonCount, at: index)
        count += comparisonCount
    }
    print(count)
}

func findIndex(_ num: Int) -> Int{
    var left = 0
    var right = cards.count - 1
    while left <= right {
        let mid = (left + right) / 2
        if cards[mid] == num {
            return mid
        }
        else if cards[mid] < num {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return left
}

→ 정답은 맞췄지만, 1544ms 이라는 오랜 시간이 걸렸다. 아마 시간 제한이 1초였다면 시간 초과에 걸렸을 거다

 

정답자들의 코드를 보니 힙으로 푸는 방법이 있는 것 같다

힙을 공부해보고 다시 풀어봐야겠다