[프로그래머스] 코딩테스트 예제 'N으로 표현' Solution in Swift

문제 출처

프로그래머스

 

---

문제

아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다.

12 = 5 + 5 + (5 / 5) + (5 / 5)
12 = 55 / 5 + 5 / 5
12 = (55 + 5) / 5

5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다.
이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요.

제한사항

• N은 1 이상 9 이하입니다.

• number는 1 이상 32,000 이하입니다.

• 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다.

• 최솟값이 8보다 크면 -1을 return 합니다.

입출력 예

N	number	return
5	12	4
2	11	3

입출력 예 설명

예제 #1
문제에 나온 예와 같습니다.

예제 #2
11 = 22 / 2와 같이 2를 3번만 사용하여 표현할 수 있습니다.

 

 

---

Solution

	//
	// ExpressedAsN.swift
	// ProgrammingProblems
	//
	// Copyright © 2020 roseMelon. All rights reserved.
	//
	import Foundation
	func solution(_ N:Int, _ number:Int) -> Int {
	if N == number { return 1 }
	return step(state: [[],[N],[justNumber(N, reapeat: 2), N*N, N+N, 1]], N: N, counter: 2, Number: number)
	}
	func step(state: [Set<Int>], N: Int, counter: Int, Number: Int) -> Int {
	if counter > 8 { return -1 }
	if let last = state.last, last.contains(Number) { return counter }
	var newState: Set<Int> = [justNumber(N, reapeat: counter + 1)]
	for i in 1..<counter+1 {
	state[i].forEach { x in
	state[counter+1 - i].forEach { y in
	let newValues = [x+y, x-y, x/y, x*y]
	newValues.forEach { new in
	guard new != 0 else { return }
	newState.insert(new)
	}
	}
	}
	}
	return step(state: state + [newState], N: N, counter: counter + 1, Number: Number)
	}
	func justNumber(_ N: Int, reapeat: Int) -> Int {
	return Int(String(repeating: String(N), count: reapeat))!
	}

view raw ExpressedAsN.swift hosted with ❤ by GitHub

 

---