2309번: 일곱 난쟁이

이중 반복문 풀이

알고리즘: 브루탈 포스
난이도: 브론즈 2

9개의 배열에서 2개를 빼고 합이 100이 되는지 확인하면 되는 문제입니다. 파이썬으로 풀 때는 itertools의 combination을 사용해서 풀었는데 아쉽게도 swift에는 기본적으로 조합을 제공해주지 않습니다.

조합을 직접 구현하는 것 보다 이중 반복문으로 구현하는 것이 빨라서 이중 반복문으로 해보았습니다.

// 입력을 받을 빈 배열
var heights: [Int] = []

// 일곱 난쟁이가 아닌 사람들의 키를 담을 변수
var a: Int = 0
var b: Int = 0

// 여러 줄 입력 받기
for _ in 1...9 {
    heights.append(Int(readLine()!)!)
}

var heightSum = heights.reduce(0, +)

// 이중 for 문을 탈출하는 방법
outerRoop: for i in 0...7 {
    for j in (i + 1)...8 {
        a = heights[i]
        b = heights[j]
        if heightSum - a - b == 100 {
            break outerRoop
        }
    }
}

// 난쟁이가 아닌 a와 b의 index를 찾아서 remove
heights.remove(at: heights.firstIndex(of: a)!)
heights.remove(at: heights.firstIndex(of: b)!)

// 정렬하기
heights.sort()

for i in 0..<heights.count {
    print(heights[i])
}

조합으로 풀이

(updated on 5/30)

이제 조합을 구현하는 방법을 공부해서 조합으로도 문제를 풀어봤습니다.

9명의 난쟁이 중에서 7명을 뽑는 조합을 만들어서 각각의 합을 구해보면 됩니다.

이 문제는 다행히도 난쟁이의 총 인원이 9명으로 고정되어 있습니다. 하지만 만약에 10명으로 난다면 반복문의 경우 3중 반복문을 사용해야 합니다. 11명이면 4중, 12명이면 5중으로 계속 반복문의 중복이 늘어나게 됩니다.

하지만 조합을 사용한다면 난쟁이가 아무리 늘어나도 동적으로 대응이 가능하다는 장점이 있습니다!

//✅ 조합 구현
func combination(array: [Int], length: Int) -> [[Int]] {
    var result = [[Int]]()
    
    func combi(nowIndex index: Int, now: [Int]) {
        if now.count == length {
            result.append(now)
            return
        }
        
        for i in index..<array.count {
            combi(nowIndex: i + 1, now: now + [array[i]])
        }
    }
    
    combi(nowIndex: 0, now: [])
    return result
}

//✅ 입력 받기
var dwarfs = [Int]()

(0..<9).forEach { _ in
    let height = Int(readLine()!)!
    dwarfs.append(height)
}

let combinations = combination(array: dwarfs, length: 7)

//✅ 조합을 순회하면서 합이 100인 조합 찾기
for combination in combinations {
    if combination.reduce(0, +) == 100 {
        combination.sorted().forEach { height in
            print(height)
        }
        break //👉 조합이 여러개인 경우 1개의 조합만 출력하고 멈추어야 한다.
    }
}