6603 swift - 로또

어떻게든 조합으로 풀어보려고 노력.

조합은 여기

[Swift] 순열 / permutation / 조합 / combination

---

문제 개요는 이것.

7 1 2 3 4 5 6 7
8 1 2 3 5 8 13 21 34
0

input의 첫번째 숫자만큼 수가 주어질 때, 그 배열에서 6개의 중복 없는 숫자를 출력하는 것.

 

 

while let readLine = readLine(), readLine != "0"{
	let input = readLine.split(separator: " ").map({Int(String($0))!})
	combi([], 0, Array(input[1..<input.count]))
	print("")
}

func combi(_ target: [Int], _ depth: Int, _ total: [Int]){
	if target.count == 6 {
		print(target.map{String($0)}.joined(separator: " "))
		return
	}
	
	for i in 0..<total.count {
		combi(target + [total[i]], depth + 1, Array(total[i+1..<total.count]))
	}
}

 

처음에 푼 방법. 기억이 안나서 어거지로 살짝 무식하게 풀었음.

while let readLine = readLine(), readLine != "0"{
	let input = readLine.split(separator: " ").map{String($0)}
	combi(Array(input[1..<input.count]), 6, 0, [])
	print("")
}

func combi(_ targetArr: [String], _ targetNum: Int, _ index: Int, _ arr: [String]) {

	if arr.count == targetNum {
		print(arr.joined(separator: " "))
		return
	}
	
	for i in index..<targetArr.count {
		combi(targetArr, targetNum, i+1, arr + [targetArr[i]])
	}
	
}

링크의 조합따라서 풀었으면 아래와 같이 쉽게 완성 됐을듯.

 

while let readLine = readLine(), readLine != "0"{
	var input = readLine.split(separator: " ").map({Int(String($0))!})
	_ = input.removeFirst()
	let result = generateCombinations(from: input)
	for i in result {
		print(i.map{String($0)}.joined(separator: " "))
	}
	print("")
}

func generateCombinations(from array: [Int], choose count: Int = 6) -> [[Int]] {
	var results = [[Int]]()
	var combination = [Int]()

	func backtrack(start: Int) {
		if combination.count == count {
			results.append(combination)
			return
		}
		
		for i in start..<array.count {
			combination.append(array[i])
			backtrack(start: i + 1)
			combination.removeLast()
		}
	}

	backtrack(start: 0)
	return results
}

backtracking으로 푼 방법.