[백준 2309] 일곱 난쟁이

2309번: 일곱 난쟁이

2309번: 일곱 난쟁이

3040번: 백설 공주와 일곱 난쟁이 문제와 동일하다.

• 이 문제는 2시간정도 고민하다가 스스로 풀기 어려워 구글링해 보았다.
• 아래는 참고한 링크들.

(Swift) 백준 2309 일곱 난쟁이

[코딩테스트 대비] 순열(Permutation)과 조합(Combination) 알고리즘

해설

• 우선은, 문제 그대로 키의 합이 100이 되는 7명을 찾는 게 아니라, 키의 합이 전체합 - 100 이 되는 나머지 2명을 찾는다는 아이디어가 필요했다.
• 찾아야 할 대상이 7개에서 2개로 줄었으므로 반복문으로도 충분히 해결이 가능해진다.
• 반복문 대신 조합(combination)으로도 풀 수 있다고 한다.
  • 순열과 조합에 대해 공부해야 할 필요성을 느꼈다.
• (추가) 이중for문 내에서 그냥 break를 하면 바깥 반복문을 탈출하지 못해 인덱스 에러가 발생할 수 있다.
  • 반드시 바깥 루프에 이름을 붙여 주고, 그 루프 전체를 탈출함을 명시해 줘야 한다.

풀이1

var inputArr: [Int] = []
for _ in 1...9 {
    let input = Int(readLine()!)!
    inputArr.append(input)
}
inputArr.sort()
let exceptSum = inputArr.reduce(0, +) - 100
outerLoop : for index1 in inputArr.indices {
    let except1 = inputArr[index1]
    for index2 in inputArr.indices {
        let except2 = inputArr[index2]
        if (except1 + except2 == exceptSum) {
            inputArr.remove(at: max(index1, index2))
            inputArr.remove(at: min(index1, index2))
            break outerLoop
        }
    }
}
for input in inputArr {
    print(input)
}

풀이2

var inputArr: [Int] = []
(1...9).forEach { _ in
    inputArr.append(Int(readLine()!)!)
}
let sum = inputArr.reduce(0, +)
let remain = sum - 100
outerLoop: for i in inputArr.indices {
    for j in inputArr.indices {
        let a = inputArr[i]
        let b = inputArr[j]
        if i != j && inputArr[i] + inputArr[j] == remain {
            inputArr.remove(at: inputArr.firstIndex(of: a)!)
            inputArr.remove(at: inputArr.firstIndex(of: b)!)
            break outerLoop // 매우 필요!
        }
    }
}
inputArr.forEach { print($0) }