[Swift] 프로그래머스 - 소수 만들기

문제

https://programmers.co.kr/learn/courses/30/lessons/12977

주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return 하도록 solution 함수를 완성해주세요.

접근방법

3개의 수를 뽑아야 하니깐 조합으로 3개의 수를 뽑고

그 수의 합이 소수이면 count += 1

return count

뽑아야 할 수가 적다면, 단순하게 for문을 뽑을 갯수만큼 만들어 주면 조합이 된다.

	let nums = [1,2,3,4,5,6,7,8]
	for i in nums.indices {
	for j in i+1..<nums.count {
	for k in j+1..<nums.count {
	print("\(nums[i])\(nums[j])\(nums[k])")
	}
	}
	}

view raw 조합1.swift hosted with ❤ by GitHub

요런식으로.. 3개를 뽑는건 for문 3개..

단 많을경우 dfs를 통해 조합을 만들어 주면 된다.

	func solution(_ nums:[Int]) -> Int {
	var count = 0
	let list = Array(repeating: 0, count: nums.count)
	// data: 데이터 리스트, list: 뽑을 데이터의 idx 정보, r: 뽑을 갯수
	dfs(data: nums, list: list, r: 3, idx: 0, depth: 0, count: &count)
	return count
	}
	func dfs(data: [Int], list: [Int], r: Int, idx: Int, depth: Int, count: inout Int) {
	if r == 0 {
	var sum = 0
	for i in 0 ..< idx {
	sum += data[list[i]] // data[list[i]]가 뽑은 item
	}
	if check(sum) {
	count += 1
	}
	} else if depth >= data.count { return }
	else {
	var list = list
	list[idx] = depth
	dfs(data: data, list: list, r: r-1, idx: idx+1, depth: depth+1, count: &count)
	dfs(data: data, list: list, r: r, idx: idx, depth: depth+1, count: &count)
	}
	}

view raw 조합2.swift hosted with ❤ by GitHub

풀이

	func solution(_ nums:[Int]) -> Int {
	var count = 0
	let list = Array(repeating: 0, count: nums.count)
	// data: 데이터 리스트, list: 뽑을 데이터의 idx 정보, r: 뽑을 갯수
	dfs(data: nums, list: list, r: 3, idx: 0, depth: 0, count: &count)
	return count
	}
	func dfs(data: [Int], list: [Int], r: Int, idx: Int, depth: Int, count: inout Int) {
	if r == 0 {
	var sum = 0
	for i in 0 ..< idx {
	sum += data[list[i]] // data[list[i]]가 뽑은 item
	}
	if check(sum) {
	count += 1
	}
	} else if depth >= data.count { return }
	else {
	var list = list
	list[idx] = depth
	dfs(data: data, list: list, r: r-1, idx: idx+1, depth: depth+1, count: &count)
	dfs(data: data, list: list, r: r, idx: idx, depth: depth+1, count: &count)
	}
	}
	func check(_ n: Int) -> Bool {
	if n < 3 { return false}
	if n == 3 { return true }
	else {
	for i in 2 ..< n {
	if n%i == 0 { return false}
	}
	}
	return true
	}
	let a = [1,2,3,4]
	print(solution(a))

view raw 소수만들기.swift hosted with ❤ by GitHub